Zeckendorf number representation
1
func fib(n) is cached {
2
n < 2 ? 1
3
: (fib(n-1) + fib(n-2))
4
}
5
6
func zeckendorf(n) {
7
n == 0 && return '0'
8
var i = 1
9
++i while (fib(i) <= n)
10
gather {
11
while (--i > 0) {
12
var f = fib(i)
13
f > n ? (take '0')
14
: (take '1'; n -= f)
15
}
16
}.join
17
}
18
19
for n (0..20) {
20
printf("%4d: %8s\n", n, zeckendorf(n))
21
}
Copied!

Output:

1
0: 0
2
1: 1
3
2: 10
4
3: 100
5
4: 101
6
5: 1000
7
6: 1001
8
7: 1010
9
8: 10000
10
9: 10001
11
10: 10010
12
11: 10100
13
12: 10101
14
13: 100000
15
14: 100001
16
15: 100010
17
16: 100100
18
17: 100101
19
18: 101000
20
19: 101001
21
20: 101010
Copied!
Last modified 1yr ago
Copy link
Contents
Output: