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.
Programming Praxis 
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):
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; list.add(num); return 0; } int fibonacciCounter = 0; int previousVal = 0; int currentVal = 0; while ((currentVal = fibonacci(fibonacciCounter)) < num) { fibonacciCounter++; previousVal = currentVal; } sum += previousVal; list.add(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); System.out.print(\"\\nFibonacci Addends: {\"); while (!results.isEmpty()) { if (results.size() == 1) System.out.print(results.pop() + \"}\"); else System.out.print(results.pop() + \", \"); } } }A Common Lisp solution (using the “iterate” package, available via Quicklisp).
Usage example:
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)))))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)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.
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.
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 resultHere’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));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)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#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 :-
?- 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]