## Zeckendorf Representation

### July 24, 2012

First we write a function that computes the fibonacci numbers not exceeding the target number n; we arrange that it return the numbers in descending order, since that’s how we will use them:

```(define (fibs n)   (let loop ((f2 1) (f1 1) (f 2) (fs (list 1 1)))     (if (< n f) fs (loop f1 f (+ f1 f) (cons f fs)))))```

Then we find the Zeckendorf representation by iterating through the fibonacci sequence, keeping track of the reducing target as we go:

```(define (zeck n)   (let loop ((n n) (fs (fibs n)) (zs (list)))     (cond ((= (car fs) n) (cons (car fs) zs))           ((< (car fs) n)             (loop (- n (car fs)) (cdr fs)                   (cons (car fs) zs)))           (else (loop n (cdr fs) zs)))))```

It seems wasteful to recompute the fibonacci sequence with each number, but the computation is very fast, and even large numbers are handled quickly:

```> (zeck 100) (3 8 89) > (zeck (expt 3 15)) (2 55 987 6765 46368 196418 1346269 3524578 9227465) > (time (length (zeck (expt 10 100)))) (time (length (zeck (...))))     no collections     0 ms elapsed cpu time     0 ms elapsed real time     45496 bytes allocated 137```

You can run the program at http://programmingpraxis.codepad.org/jSXS5a1q.

Pages: 1 2

### 16 Responses to “Zeckendorf Representation”

1. Graham said

fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

greedy :: (Integral a) => a -> a
greedy n = last \$ takeWhile (<= n) fibs

zeckendorf :: (Integral a) => a -> [a]
zeckendorf n = reverse \$ rec n where
rec 0 = []
rec x = g : rec (n – g) where g = greedy n

main :: IO ()
main = mapM_ (print . zeckendorf) [100, 3 ^ 15, 10 ^ 100]

A bit slow in the ghci interpreter, but very fast when compiled. I’m sure a Haskell guru will come along shortly with a better solution :-)

2. Graham said

Apologies for borking the posting.

3. […] today’s Programming Praxis exercise, our goal is to find a series of non-consecutive fibonacci numbers that […]

4. A small error in the description: 100 = 3 + 8 + 89, not 2 + 8 + 89 :)

```fibs :: [Integer]
fibs = 1 : scanl (+) 1 fibs

zeck :: Integer -> [Integer]
zeck 0 = []
zeck n = f : zeck (n - f) where f = last \$ takeWhile (<= n) fibs
```
5. thmsdrew said
```package fib;

import java.util.Stack;

public class Fib {
int sum = 0;
static Stack list = new Stack();

public int fibonacci(int num) {
if (num == 0)
return 0;
else if (num == 1)
return 1;
else
return fibonacci(num - 1) + fibonacci(num - 2);
}

public int zeckendorf(int num) {
if (isFibonacciNumber(num)) {
sum += num;
return 0;
}
int fibonacciCounter = 0;
int previousVal = 0;
int currentVal = 0;
while ((currentVal = fibonacci(fibonacciCounter)) < num) {
fibonacciCounter++;
previousVal = currentVal;
}
sum += previousVal;
int remainder = num - previousVal;
return zeckendorf(remainder);
}

public boolean isFibonacciNumber(int num) {
if (isPerfectSquare((5 * num * num) + 4) ||
isPerfectSquare((5 * num * num) - 4))
return true;
return false;
}

public boolean isPerfectSquare(int num) {
int sqrt = (int) Math.sqrt(num);
if (sqrt * sqrt == num)
return true;
return false;
}

public static Stack runZeck(int num) {
Fib fib = new Fib();
fib.zeckendorf(num);
return list;
}

public static void main(String[] args) {
int num = 500;
Stack results = runZeck(num);
output(num, results);
}

public static void output(int num, Stack results) {
System.out.print(\"Number: \" + num);
while (!results.isEmpty()) {
if (results.size() == 1)
System.out.print(results.pop() + \"}\");
else
System.out.print(results.pop() + \", \");
}
}
}
```
6. Jan Van lent said

A Common Lisp solution (using the “iterate” package, available via Quicklisp).

Usage example:

```CL-USER> (fib-list 100)
(1 2 3 5 8 13 21 34 55 89)
CL-USER> (zeckendorf 100)
(89 8 3)
CL-USER> (zeckendorf-binary 100)
(1 0 0 0 0 1 0 1 0 0)
```

Code:

```(use-package :iterate)

(defun fib-list (n)
"return list of Fibonacci numbers less than or equal to N"
(iter (for (a b) initially '(1 1) then (list b (+ a b)))
(while (<= b n))
(collect b)))

(defun zeckendorf (n)
(iter (with m = n)
(for f in (reverse (fib-list n)))
(while (> m 0)) ; early escape optimzation, can be removed
(when (>= m f)
(decf m f)
(collect f))))

(defun zeckendorf-binary (n)
(iter (with m = n)
(for f in (reverse (fib-list n)))
(cond ((>= m f) (decf m f) (collect 1))
(t (collect 0)))))
```
7. Jan Van lent said

Haskell solution inspired by the other Haskell solutions and the Common Lisp solution.

```fibs' :: [ Integer ]
fibs' = 1 : scanl (+) 2 fibs'

fibsDownFrom n = reverse \$ takeWhile (<n) fibs'

zeck n = zeck' n \$ fibsDownFrom n

zeck' 0 _ = []
zeck' n (f:fs) = if n >= f
then f : (zeck' (n-f) fs)
else zeck' n fs

zeckBin n = zeckBin' n \$ fibsDownFrom n

zeckBin' _ [] = []
zeckBin' n (f:fs) = if n >= f
then 1 : (zeckBin' (n-f) fs)
else 0 : (zeckBin' n fs)
```
8. Jan Van lent said

`(<n)`

it should be

`(<=n)`

.

9. ardnew said

Here’s an approach using the closed form representation of Fibonacci numbers. It solves the closed form F(n) = m for n to determine the largest Fibonacci number less than the target.

```use strict;
use warnings;

our \$PHI = (1 + sqrt(5)) / 2;

sub solve
{
return int(\$PHI ** (int(log(sqrt(5) * ((shift) + 0.5)) / log(\$PHI))) / sqrt(5) + 0.5);
}

die "usage:\$/\tperl \$0 <positive integer>\$/" unless
@ARGV > 0 and \$ARGV =~ /^[0-9]+\$/;

my (\$n, \$m) = (\$ARGV, 0);

print(\$m = solve(\$n)." "), \$n -= \$m while \$n;
```

Due to the limitations of Perl, some rounding error may occur when feeding it large inputs.

10. MVUTMJAWRZ said
```def zeck(n):
a,b = 0,1
while b <= n:
a,b = b,a+b
result = []
while n > 0:
if a <= n:
result.append(a)
n -= a
a,b = b-a,a
return result
```
11. Here’s a JavaScript solution:

```function remove(element, index, array){return element <= this;}

function get_fibonacci_sequence_less_than(n){
var fib = [0, 1];

while(fib[fib.length - 1] < n)
{
fib.push(fib[fib.length - 1] + fib[fib.length - 2]);
}

return fib.filter(remove, n);
}

function get_zeckendorf_of(n){
var fib = get_fibonacci_sequence_less_than(n);
var sol = [];
var i   = 0;
var sum = n;

while(true){
n = n - fib[fib.length - 1];
sol.push(fib[fib.length - 1]);
fib = fib.filter(remove, n);

if(sol.reduce(function(a,b){return a+b}) == sum)
break;
}

return sol;
}

console.log(get_zeckendorf_of(100));
console.log(get_zeckendorf_of(14348907));
```
12. Another Python solution:

```def fibs(n):
fs = 
f = 1
while f <= n:
fs.append(f)
f = fs[-1] + fs[-2]
return fs

def zeckendorf(n):
fs = fibs(n)
fs.reverse()
result = []
while n > 0:
for f in fs:
if f <= n:
result.append(f)
n -= f
result.reverse()
return result

def solve(n):
print("%d = %s" % (n, ' + '.join(map(str, zeckendorf(n)))))

solve(100)
```
13. David said

Forth solution, table look up based.

```
create F32  \ all fibonaccis that fit in 32 bits
here
1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 , 89 , 144 , 233 , 377 , 610 , 987 ,
1597 , 2584 , 4181 , 6765 , 10946 , 17711 , 28657 , 46368 , 75025 ,
121393 , 196418 , 317811 , 514229 , 832040 , 1346269 , 2178309 , 3524578 ,
5702887 , 9227465 , 14930352 , 24157817 , 39088169 ,  63245986 , 102334155 ,
165580141 , 267914296 , 433494437 , 701408733 , 1134903170 , 1836311903 ,

here swap - cell/ Constant #F32

: sgn ( n -- n )
dup 0< swap 0> - ;

: bsearch ( n addr c -- n )   \ find n, or largest int < n
0 0 locals| m l h table n |
BEGIN  l h <  WHILE
h l + 2/ to m
m cells F32 + @ n - sgn CASE
0 OF  m EXIT      ENDOF
-1 OF  m 1+ to l   ENDOF
1 OF  m to h      ENDOF
ENDCASE
REPEAT
h 1- ;

: F<=  ( n -- n )   \ largest Fibonacci <= n
F32 #F32 bsearch cells F32 + @ ;

: z. ( n -- )
dup F<= dup . -
BEGIN ?dup WHILE
dup F<= dup [char] + emit space . -
REPEAT ;

100 z. 89 + 8 + 3  ok
256 z. 233 + 21 + 2  ok
750 z. 610 + 89 + 34 + 13 + 3 + 1  ok
1000 z. 987 + 13  ok
```
14. Ajay Kumar said

#include
#include
void main()
{
int n,f,k,s=0;
f=0;
f=1;
clrscr();
cout<>n;
cout<<f<<endl<<f;
for(int i=2;i<n;i++)
{
f[i]=f[i-1]+f[i-2];
cout<<endl<<f[i];
}
cout<>k;
cout<<k<=0;i–)
if(k>=f[i])
{
s=f[i];
break;
}
k=k-s;
cout<<s<<"+";
}
cout<<"0";
getch();
}

15. David said

Redid in Prolog :-

```?- dynamic(fibo/2).

fibo(0, 1).
fibo(1, 1).

fibonacci(N, F) :- fibo(N, F), !.
fibonacci(N, F) :-
succ(N1, N),  fibonacci(N1, F1),
succ(N2, N1), fibonacci(N2, F2),
F is F1 + F2,
assertz(fibo(N, F)).

nat(0).
nat(N) :- nat(M), succ(M, N).

fib_seq(Limit, X) :-
nat(N),
fibonacci(N, F),
(F =< Limit -> X = F ; !, fail).

fib_le(Limit, N) :-
setof(Z, fib_seq(Limit, Z), S),
last(S, N).

zeck(0, []) :- !.
zeck(N, [F|Fs]) :-
fib_le(N, F),
plus(F, N2, N),
zeck(N2, Fs).

?- zeck(100, Z), write('Zeck 100 = '), write(Z), nl.
Zeck 100 = [89,8,3]
```