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