## Zeckendorf Representation

### July 24, 2012

The folks at /r/dailyprogrammer publish programming exercises on a regular basis; you might want to have a look. They frequently steal my exercises, so today I will steal one of theirs.

Any positive integer can be represented as the sum of one or more non-consecutive fibonacci numbers. For instance, 100 = 2 + 8 + 89. Note that 100 can also be written using fibonacci sums as 89 + 8 + 2 + 1 or 55 + 34 + 8 + 3, but those use consecutive fibonacci numbers (2 + 1 for the first representation, 55 + 34 for the second). Belgian mathematician Edouard Zeckendorf proved that such a representation is unique.

Zeckendorf representations can easily be found by a greedy strategy. Start with the largest fibonacci number less than the target number. Then choose the largest fibonacci number less than the remainder after subtracting the first number. And so on, stopping when the remainder is a fibonacci number itself.

Your task is to write a function that finds the Zeckendorf representation of a positive integer. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

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] =~ /^[0-9]+\$/;

my (\$n, \$m) = (\$ARGV[0], 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 = [1]
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[20],k,s=0;
f[0]=0;
f[1]=1;
clrscr();
cout<>n;
cout<<f[0]<<endl<<f[1];
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]
```