Zeckendorf number representation

Zeckendorf number representation
You are encouraged to solve this task according to the task description, using any language you may know.

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

• Fibonacci sequence
• Brown's Criterion - Numberphile

C

<lang c>#include <stdio.h>

typedef unsigned long long u64;

1. define FIB_INVALID (~(u64)0)

u64 fib[] = { 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, 2971215073ULL, 4807526976ULL, 7778742049ULL, 12586269025ULL, 20365011074ULL, 32951280099ULL, 53316291173ULL, 86267571272ULL, 139583862445ULL, 225851433717ULL, 365435296162ULL, 591286729879ULL, 956722026041ULL, 1548008755920ULL, 2504730781961ULL, 4052739537881ULL, 6557470319842ULL, 10610209857723ULL, 17167680177565ULL,

27777890035288ULL // this 65-th one is for range check };

u64 fibbinary(u64 n) { if (n >= fib[64]) return FIB_INVALID;

u64 ret = 0; int i; for (i = 64; i--; ) if (n >= fib[i]) { ret |= 1ULL << i; n -= fib[i]; }

return ret; }

void bprint(u64 n, int width) { if (width > 64) width = 64;

u64 b; for (b = 1ULL << (width - 1); b; b >>= 1) putchar(b == 1 && !n ? '0' : b > n ? ' ' : b & n ? '1' : '0'); putchar('\n'); }

int main(void) { int i;

for (i = 0; i <= 20; i++) printf("%2d:", i), bprint(fibbinary(i), 8);

return 0; }</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

Common Lisp

Common Lisp's arbitrary precision integers should handle any positive input: <lang lisp>(defun zeckendorf (n)

  "returns zeckendorf integer of n (see OEIS A003714)"
  (let ((fib '(2 1)))

;; extend Fibonacci sequence long enough (loop while (<= (car fib) n) do (push (+ (car fib) (cadr fib)) fib)) (loop with r = 0 for f in fib do (setf r (* 2 r)) (when (>= n f) (setf n (- n f)) (incf r)) finally (return r))))

task requirement

(loop for i from 0 to 20 do

     (format t "~2D: ~2R~%" i (zeckendorf i)))</lang>

<lang lisp>

Print Zeckendorf numbers upto 20.

I have implemented this as a state machine.

Nigel Galloway - October 13th., 2012

(let ((fibz '(13 8 5 3 2 1))) (dotimes (G 21) (progn (format t "~S is " G)

  (let ((z 0) (ng G)) (dolist (N fibz)
    (if (> z 1) (progn (setq z 1) (format t "~S" 0))
      (if (>= ng N) (progn (setq z 2) (setq ng (- ng N)) (format t "~S" 1))
        (if (= z 1) (format t "~S" 0)))))
  (if (= z 0) (format t "~S~%" 0) (format t "~%"))))))

</lang>

Output:

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

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:

0
1
10
100
101
1000
1001
1010
10000
10001
10010
10100
10101
100000
100001
100010
100100
100101
101000
101001
101010

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(1, 1, n, 0)[1];

}

void main() {

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

}</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

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, 2)
   //             .takeWhile!(x => x <= n)()
   //             .array();
   int[] fibs;
   foreach (f; recurrence!q{a[n - 1] + a[n - 2]}(1, 2))
       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: %6s", i, zeckendorf(i));

}</lang>

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 {

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

}

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

   if fib1 > n {
       return n, 0
   }
   // recurse.
   // construct sequence on the way in, construct ZR on the way out.
   remaining, set = zr(fib1, fib0+fib1, n, bit+1)
   if fib1 <= remaining {
       set |= 1 << bit
       remaining -= fib1
   }
   return

}</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

Haskell

Using "no consecutive 1s" rule: <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> which is the same as <lang haskell>zeckendorf = "0":"1":[s++[d] | s <- tail zeckendorf, d <- "01", last s /= '1' || d /= '1']

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>

Creating a string for an individual number: <lang haskell>fib = 1 : 2 : zipWith (+) fib (tail fib)

zeckendorf 0 = "0" zeckendorf n = f n (reverse $ takeWhile (<=n) fib) where f _ [] = "" f n (x:xs) | n < x = '0' : f n xs | True = '1' : f (n - x) xs

main = mapM (putStrLn . zeckendorf) [0..20]</lang>

Output:

0
1
10
100
101
1000
1001
1010
10000
10001
10010
10100
10101
100000
100001
100010
100100
100101
101000
101001
101010

Perl 6

<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, 2]
   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]
  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

Shorter version

<lang python>n = 20 def z(n):

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

REXX

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

• 11.10.2012 Walter Pachl
  • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • /

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

 Parse Var fib f.i fib             /* f.1 ... 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=6 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,6)     /* show result                   */
 End</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

Tcl

<lang tcl>package require Tcl 8.5

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

proc fibseq target {

   set seq {}; set prev 1; set fib 1
   for {set n 1;set i 1} {$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

}

1. 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:        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

XPL0

<lang XPL0>include c:\cxpl\codes; \intrinsic 'code' declarations

proc Zeckendorf(N); \Display Zeckendorf number (N <= 20) int N; int Fib, LZ, I; [Fib:= [1, 2, 3, 5, 8, 13]; \Fibonacci sequence LZ:= true; \suppress leading zeros for I:= 5 downto 0 do

       [if N >= Fib(I) then [N:= N-Fib(I);  ChOut(0, ^1);  LZ:= false]
       else ChOut(0, if LZ then ^  else ^0);
       ];

];

int N; [for N:= 0 to 20 do

       [if N<10 then ChOut(0,^ );  IntOut(0, N);  Text(0, ": ");
       Zeckendorf(N);  CrLf(0);
       ];

]</lang>

Output:

 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