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.

About these ads

Pages: 1 2

16 Responses to “Zeckendorf Representation”

  1. Graham said

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

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

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

    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;
                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() + \", \");
            }
        }
    }
    
  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

    There is a mistake in my Haskell solution. Instead of

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 598 other followers

%d bloggers like this: