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.



Task

Generate and show here a table of the Zeckendorf number representations of the decimal numbers zero to twenty, in order.

The intention in this task to find the Zeckendorf form of an arbitrary integer. The Zeckendorf form can be iterated by some bit twiddling rather than calculating each value separately but leave that to another separate task.



Also see

   OEIS A014417   for the the sequence of required results.
   Brown's Criterion - Numberphile


Related task

   Fibonacci sequence


 
// Little Man Computer, for Rosetta Code.
// Writes Zeckendorf representations of numbers 0..20.
// Works with Peter Higginson's LMC simulator, except that
//   user must intervene manually to capture all the output.
         LDA c0       // initialize to N = 0
loop     STA N
         OUT          // write N
         LDA equals   // then equals sign
         OTC
         BRA wr_zeck  // then Zeckendorf rep
return   LDA space    // then space
         OTC
         LDA N        // done maximum N?
         SUB N_max
         BRZ halt     // yes, halt
         LDA N        // no, inc N and loop back
         ADD c1
         BRA loop
halt     HLT
c0       DAT 0
N_max    DAT 20
equals   DAT 61
space    DAT 32
 
// Routine to write Zeckendorf representation of number stored in N.
// Since LMC doesn't support subroutines, returns with "BRA return".
wr_zeck  LDA N
         SUB c1
         BRP phase_1
// N = 0, special case
         LDA ascii_0
         OTC
         BRA done
// N > 0. Phase 1: find largest Fibonacci number <= N
phase_1  STA res      // res := N - 1
         LDA c1       // initialize Fibonacci terms
         STA a
         STA b
loop_1   LDA res      // here res = N - a (easy proof)
         SUB b        // is next Fibonacci a + b > N?
         BRP next_fib // no, continue Fibonacci
         BRA phase_2  // yes, on to phase 2
next_fib STA res      // res := res - b
         LDA a        // (a, b) := (a + b, a)
         ADD b
         STA a
         SUB b
         STA b
         BRA loop_1   // loop to test new (a, b)
// Phase 2: get Zeckendorf digits by winding Fibonacci back
phase_2  LDA ascii_1  // first digit must be 1
         OTC
loop_2   LDA a        // done when wound back to a = 1
         SUB c1
         BRZ done
         LDA res      // decide next Zeckendorf digit
         SUB b        // 0 if res < b, 1 if res >= b
         BRP dig_is_1
         LDA ascii_0
         BRA wr_dig
dig_is_1 STA res      // res := res - b
         LDA ascii_1
wr_dig   OTC          // write Zeckendorf digit 0 or 1
         LDA a        // (a, b) := (b, a - b)
         SUB b
         STA b
         LDA a
         SUB b
         STA a
         BRA loop_2   // loop to test new (a, b)
done     BRA return
N        DAT
res      DAT
a        DAT
b        DAT
c1       DAT 1
ascii_0  DAT 48
ascii_1  DAT 49
// end
 