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

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