## 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.

Trying to win the race to post a Haskell answer:

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 :-)

Apologies for borking the posting.

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

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

My Haskell solution (see http://bonsaicode.wordpress.com/2012/07/24/programming-praxis-zeckendorf-representation/ for a version with comments):

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

Usage example:

Code:

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

There is a mistake in my Haskell solution. Instead of

it should be

.

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.

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

Here’s a JavaScript solution:

Another Python solution:

Forth solution, table look up based.

#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();

}

[…] Pages: 1 2 […]

Redid in Prolog :-