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 members of the Fibonacci series.

Recall that the first seven Fibonacci numbers are: 13, 8, 5, 3, 2, 1, 1 (written right-to left). The decimal number eleven can be written as 0*13 + 1*8 + 0*5 + 1*3 + 0*2 + 0*1 + 0*1 or 0101000 in positional notation where the columns represent multiplication by a particular member of the series. Leading zeroes are dropped so that 11 decimal becomes 101000.

101000 is not the only way to make 11 from the Fibonacci sequance however; 0*13 + 1*8 + 0*5 + 0*3 + 1*2 + 1*1 + 0*1 or 0100110 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.

Task specifics

It turns out that a greedy algorithm that uses the next member of the sequence less than or equal to the remainder of the number being converted will generate the Zeckendorf number representation. The task is to generate and show here a table of the Zeckendorf number representation of the decimal numbers zero to twenty, in order.

Cf:

Go

<lang go>package main

import "fmt"

func main() {

   for i := 0; i <= 20; i++ {
       fmt.Printf("%2d %7b\n", i, zeckendorf(i))
   }

}

func zeckendorf(n int) int {

   _, set := zr(1, 1, n, 0)
   return set

}

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

   switch {
   case fib1 > n:
       return n, 0
   case fib1 == n:
       return fib1 - n, 1 << bit
   }
   remaining, set = zr(fib1, fib0+fib1, n, bit+1)
   if fib1 <= remaining {
       set |= 1 << bit
       remaining -= fib1
   }
   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 . (zeckendorf!!)) [0..20]</lang>

Output:

Perl 6

We're going with the sequence that doesn't duplicate 1 here. <lang perl6>printf "%2d: %8s\n", $_, zeckendorf($_) for 0 .. 20;

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

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

}</lang>

Output:

 0:        0
 1:        1
 2:       10
 3:      100
 4:      101
 5:     1000
 6:     1001
 7:     1010
 8:    10000
 9:    10001
10:    10010
11:    10100
12:    10101
13:   100000
14:   100001
15:   100010
16:   100100
17:   100101
18:   101000
19:   101001
20:   101010

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

Python:Shorter version

<lang python>def z(n):

   if n == 0 : return [0]
   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:       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