Integer sequences

Fibonacci sequence

# Recursive
function fix(F)
  m = {}
  return fn g|n|
    if n not in m then m[n] = F(g,n) end
    return m[n]
  end
end

fib = fix(|f,n| 1 if n in 1..2 else f(n-1)+f(n-2))


# As a dynamic system
Fib = |[x,y]| [x+y,x]
fib = |n| (Fib^n)([0,1])[0]


# By a general algorithm for
# a(n) := f(n,a(n-2),a(n-1))
rec = |a0,a1,f| fn|n|
  x,y = a0,a1
  for k in 0..n-1
    x,y = y,f(k,x,y)
  end
  return x
end

fib = rec(0,1,|n,x,y| x+y)

Collatz conjecture

collatz = |n| n//2 if n%2==0 else 3*n+1

for x in 1..20
  a = collatz.orbit(x).until(|n| n==1).list()
  print(a)
end

function tab(m)
  d = {}
  for x in 1..m
    i = collatz.orbit(x)
    a = i()
    for b in i
      if b in d
        d[b].add(a)
        break
      end
      d[b] = {a}
      a = b
    end
  end
  d[4] = {8}
  return d
end

function tree(n,d,s,max)
  if s<max
    print("| "*s,n)
    if n in d
      for x in list(d[n]).sort()
        tree(x,d,s+1,max)
      end
    end
  end
end

tree(1,tab(100),0,20)