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.

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 574 other followers

%d bloggers like this: