Zeckendorf number representation

Just as numbers can be represented in a positional notation as sums of multiples of the powers of ten (decimal) or two (binary); all the positive integers can be represented as the sum of one or zero times the distinct members of the Fibonacci series.

Recall that the first six distinct Fibonacci numbers are: 1, 2, 3, 5, 8, 13. The decimal number eleven can be written as 0*13 + 1*8 + 0*5 + 1*3 + 0*2 + 0*1 or 010100 in positional notation where the columns represent multiplication by a particular member of the sequence. Leading zeroes are dropped so that 11 decimal becomes 10100.

10100 is not the only way to make 11 from the Fibonacci nubmers however; 0*13 + 1*8 + 0*5 + 0*3 + 1*2 + 1*1 or 010011 would also represent decimal 11. For a true Zeckendorf number there is the added restriction that that no two consecutive Fibonacci numbers can be used which leads to the former unique solution.

The task is to generate and show here a table of the Zeckendorf number representations of the decimal numbers zero to twenty, in order. See OEIS A014417 for the the sequence of required results. Cf:

D

Translation of: Haskell

<lang d>import std.stdio, std.range, std.algorithm;

void main() {

   writefln("%(%b\n%)", iota(size_t.max)
                        .filter!q{ !(a & (a >> 1)) }()
                        .take(21));

}</lang>

Output:

Translation of: Go

<lang d>import std.stdio, std.typecons;

int zeckendorf(in int n) pure nothrow {

    Tuple!(int,"remaining", int,"set")
    zr(in int fib0, in int fib1, in int n, in uint bit) pure nothrow {
       if (fib1 > n)
           return typeof(return)(n, 0);
       auto rs = zr(fib1, fib0 + fib1, n, bit + 1);
       if (fib1 <= rs.remaining) {
           rs.set |= 1 << bit;
           rs.remaining -= fib1;
       }
       return rs;
   }

   return zr(0, 1, n, 0)[1];

}

void main() {

   foreach (i; 0 .. 21)
       writefln("%2d: %7b", i, zeckendorf(i));

}</lang>

Output:

 0:       0
 1:      10
 2:     100
 3:    1000
 4:    1010
 5:   10000
 6:   10010
 7:   10100
 8:  100000
 9:  100010
10:  100100
11:  101000
12:  101010
13: 1000000
14: 1000010
15: 1000100
16: 1001000
17: 1001010
18: 1010000
19: 1010010
20: 1010100

Translation of: Tcl

(Same output.) <lang d>import std.stdio, std.algorithm, std.range, std.conv;

string zeckendorf(size_t n) {

   if (n == 0) return "0";
   //const fibs = recurrence!q{a[n - 1] + a[n - 2]}(1, 1)
   //             .takeWhile!(x => x <= n)()
   //             .array();
   int[] fibs;
   foreach (f; recurrence!q{a[n - 1] + a[n - 2]}(1, 1))
       if (f <= n)
           fibs ~= f;
       else
           break;
   string result;
   foreach_reverse (f; fibs) {
       int z = f <= n;
       result ~= text(z);
       if (z)
           n -= f;
   }
   return result;

}

void main() {

   foreach (i; 0 .. 21)
       writefln("%2d: %7s", i, zeckendorf(i));

}</lang>

Go

<lang go>package main

import "fmt"

func main() {

   for i := 0; i <= 20; i++ {
       // TS4: leading zeros not printed with %b
       fmt.Printf("%2d %7b\n", i, zeckendorf(i))
   }

}

func zeckendorf(n int) int {

   // TS1: initial arguments of fib0 = 0 and fib1 = 1 will produce
   // the Fibonacci sequence {1, 1, 2, 3,..} on the stack as successive
   // values of fib1.
   _, set := zr(0, 1, n, 0)
   return set

}

func zr(fib0, fib1, n int, bit uint) (remaining, set int) {

   if fib1 > n {
       // TS2a: sequence limit.
       // sequence ends where fib1 <= n, so we watch for fib1 to
       // exceed n, then terminate recursion, throwing this term away.
       // That is, we return initial conditions for constructing ZR,
       // with the required sequence on the stack.
       return n, 0
   }
   // TS3: recurse.
   // construct sequence on the way in, construct ZR on the way out.
   remaining, set = zr(fib1, fib0+fib1, n, bit+1)
   // TS2b: accumulate digits
   if fib1 <= remaining {
       set |= 1 << bit
       remaining -= fib1
   }
   // TS5: return value "set" contains the answer.
   return

}</lang>

Output:

Haskell

<lang haskell>import Data.Bits import Numeric

zeckendorf = map b $ filter ones [0..] where ones :: Int -> Bool ones x = 0 == x .&. (x `shiftR` 1) b x = showIntAtBase 2 ("01"!!) x ""

main = mapM putStrLn $ take 21 zeckendorf</lang> or a different way to generate the sequence: <lang haskell>import Numeric

fib = 1 : 1 : zipWith (+) fib (tail fib) pow2 = iterate (2*) 1

zeckendorf = map b z where z = 0:concat (zipWith f fib pow2) f x y = map (y+) (take x z) b x = showIntAtBase 2 ("01"!!) x ""

main = mapM putStrLn $ take 21 zeckendorf</lang>

Output:

Perl 6

<lang perl6>printf "%2d: %8s\n", $_, zeckendorf($_) for 0 .. 20;

multi zeckendorf(0) { '0' } multi zeckendorf($n is copy) {

   constant FIBS = 1,1, *+* ... *;
   join , map {
       $n -= $_ if my $digit = $n >= $_;
       +$digit;
   }, reverse FIBS ...^ * > $n;

}</lang>

Output:

 0:        0
 1:       10
 2:      100
 3:     1000
 4:     1010
 5:    10000
 6:    10010
 7:    10100
 8:   100000
 9:   100010
10:   100100
11:   101000
12:   101010
13:  1000000
14:  1000010
15:  1000100
16:  1001000
17:  1001010
18:  1010000
19:  1010010
20:  1010100

Python

<lang python>def fib():

   memo = [1, 1]
   while True:
       memo.append(sum(memo))
       yield memo.pop(0)

def sequence_down_from_n(n, seq_generator):

   seq = []
   for s in seq_generator():
       seq.append(s)
       if s >= n: break
   return seq[::-1]

def zeckendorf(n):

   if n == 0: return [0]
   seq = sequence_down_from_n(n, fib)
   digits, nleft = [], n
   for s in seq:
       if s <= nleft:
           digits.append(1)
           nleft -= s
       else:
           digits.append(0)
   assert nleft == 0, 'Check all of n is accounted for'
   assert sum(x*y for x,y in zip(digits, seq)) == n, 'Assert digits are correct'
   while digits[0] == 0:
       # Remove any zeroes padding L.H.S.
       digits.pop(0)
   return digits

n = 20 print('Fibonacci digit multipliers: %r' % sequence_down_from_n(n, fib)) for i in range(n + 1):

   print('%3i: %8s' % (i, .join(str(d) for d in zeckendorf(i))))</lang>

Output:

Fibonacci digit multipliers: [21, 13, 8, 5, 3, 2, 1, 1]
  0:        0
  1:        1
  2:      100
  3:     1000
  4:     1010
  5:    10000
  6:    10010
  7:    10100
  8:   100000
  9:   100010
 10:   100100
 11:   101000
 12:   101010
 13:  1000000
 14:  1000010
 15:  1000100
 16:  1001000
 17:  1001010
 18:  1010000
 19:  1010010
 20:  1010100

Shorter version

<lang python>def z(n):

   if n == 0 : return [0]
   if n == 1 : return [1]
   fib = [1,1]
   while fib[0] < n: fib[0:0] = [sum(fib[:2])]
   dig = []
   for f in fib:
       if f <= n:
           dig, n = dig + [1], n - f
       else:
           dig += [0]
   return dig if dig[0] else dig[1:]

for i in range(n + 1):

   print('%3i: %8s' % (i, .join(str(d) for d in z(i))))</lang>

Output:

  0:        0
  1:        1
  2:      100
  3:     1000
  4:     1010
  5:    10000
  6:    10010
  7:    10100
  8:   100000
  9:   100010
 10:   100100
 11:   101000
 12:   101010
 13:  1000000
 14:  1000010
 15:  1000100
 16:  1001000
 17:  1001010
 18:  1010000
 19:  1010010
 20:  1010100

REXX

<lang rexx> /* REXX ***************************************************************

11.10.2012 Walter Pachl
- - - - /

fib='13 8 5 3 2 1 1' Do i=7 To 1 By -1 /* Prepare Fibonacci Numbers */

 Parse Var fib f.i fib             /* f.0 ... f.7                   */
 End

Do n=0 To 20 /* for all numbers in the task */

 m=n                               /* copy of number                */
 r=                              /* result for n                  */
 Do i=7 To 1 By -1                 /* loop through numbers          */
   If m>=f.i Then Do               /* f.i must be used              */
     r=r||1                        /* 1 into result                 */
     m=m-f.i                       /* subtract                      */
     End                                                              
   Else                            /* f.i is larger than the rest   */
     r=r||0                        /* 0 into result                 */
   End                                                                
 r=strip(r,'L','0')                /* strip leading zeros           */
 If r= Then r='0'                /* take care of 0                */
 Say right(n,2)':  'right(r,7)     /* show result                   */
 End</lang>

Output:

 
 0:        0 
 1:       10 
 2:      100 
 3:     1000 
 4:     1010 
 5:    10000 
 6:    10010 
 7:    10100 
 8:   100000 
 9:   100010 
10:   100100 
11:   101000 
12:   101010 
13:  1000000 
14:  1000010 
15:  1000100 
16:  1001000 
17:  1001010 
18:  1010000 
19:  1010010 
20:  1010100

Tcl

<lang tcl>package require Tcl 8.5

Generates the Fibonacci sequence (starting at 1) up to the largest item that
is no larger than the target value. Could use tricks to precompute, but this
is actually a pretty cheap linear operation.

proc fibseq target {

   set seq {}; set prev 1; set fib 1
   for {set n 1;set i 2} {$fib <= $target} {incr n} {

for {} {$i < $n} {incr i} { lassign [list $fib [incr fib $prev]] prev fib } if {$fib <= $target} { lappend seq $fib }

   }
   return $seq

}

Produce the given Zeckendorf number.

proc zeckendorf n {

   # Special case: only value that begins with 0
   if {$n == 0} {return 0}
   set zs {}
   foreach f [lreverse [fibseq $n]] {

lappend zs [set z [expr {$f <= $n}]] if {$z} {incr n [expr {-$f}]}

   }
   return [join $zs ""]

}</lang> Demonstration <lang tcl>for {set i 0} {$i <= 20} {incr i} {

   puts [format "%2d:%9s" $i [zeckendorf $i]]

}</lang>

Output:

 0:        0
 1:       10
 2:      100
 3:     1000
 4:     1010
 5:    10000
 6:    10010
 7:    10100
 8:   100000
 9:   100010
10:   100100
11:   101000
12:   101010
13:  1000000
14:  1000010
15:  1000100
16:  1001000
17:  1001010
18:  1010000
19:  1010010
20:  1010100