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 sequence 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. To avoid variability:
- The Fibonacci sequence should begin with the two integers 1 and 1.
- Starting from a reverse sequence of fibonacci numbers where the greatest is a number less than or equal to the decimal for conversion, greedily subtract the next fibonacci number and accumulate a '1' digit of the answer if the next fibonacci is less than or equal to the remaining decimal; or accumulate a digit zero of the answer, (answer digits are accumulated left to right).
- repeat by moving down to the previous member of the sequence and repeat until all members of thesequence have accumulated a digit of the answer.
- Remove the rightmost, (most significant), digit if it is zero.
- Return the digits as the answer.
Cf:
D
<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
<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
(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:
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
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:
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,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