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


*        Zeckendorf number representation  04/04/2017
ZECKEN   CSECT
         USING  ZECKEN,R13         base register
         B      72(R15)            skip savearea
         DC     17F'0'             savearea
         STM    R14,R12,12(R13)    save previous context
         ST     R13,4(R15)         link backward
         ST     R15,8(R13)         link forward
         LR     R13,R15            set addressability
         LA     R6,0               i=0
       DO WHILE=(C,R6,LE,=A(20))   do i=0 to 20
         MVC    PG,=CL80'xx : '      init buffer
         LA     R10,PG               pgi=0
         XDECO  R6,XDEC              i
         MVC    0(2,R10),XDEC+10     output i
         LA     R10,5(R10)           pgi+=5
         MVC    FIB,=A(1)            fib(1)=1
         MVC    FIB+4,=A(2)          fib(2)=2
         LA     R7,2                 j=2
         LR     R1,R7                j
         SLA    R1,2                 @fib(j)
       DO WHILE=(C,R6,GT,FIB-4(R1)   do while fib(j)<i
         LA     R7,1(R7)               j++
         LR     R1,R7                  j
         SLA    R1,2                   ~
         L      R2,FIB-8(R1)           fib(j-1)
         A      R2,FIB-12(R1)          fib(j-2)
         ST     R2,FIB-4(R1)           fib(j)=fib(j-1)+fib(j-2)
         LR     R1,R7                  j
         SLA    R1,2                   @fib(j)
       ENDDO    ,                    enddo j
         LR     R8,R6                k=i
         MVI    BB,X'00'             bb=false
       DO WHILE=(C,R7,GE,=A(1))      do j=j to 1 by -1
         LR     R1,R7                  j
         SLA    R1,2                   ~
       IF C,R8,GE,FIB-4(R1) THEN       if fib(j)<=k then
         MVI    BB,X'01'                 bb=true
         MVC    0(1,R10),=C'1'           output '1'
         LA     R10,1(R10)               pgi+=1
         LR     R1,R7                    j
         SLA    R1,2                     ~
         S      R8,FIB-4(R1)             k=k-fib(j)
       ELSE     ,                      else
       IF CLI,BB,EQ,X'01' THEN           if bb then
         MVC    0(1,R10),=C'0'             output '0'
         LA     R10,1(R10)                 pgi+=1
       ENDIF    ,                        endif
       ENDIF    ,                      endif
         BCTR   R7,0                   j--
       ENDDO    ,                    enddo j
       IF CLI,BB,NE,X'01' THEN       if not bb then
         MVC    0(1,R10),=C'0'         output '0'
       ENDIF    ,                    endif
         XPRNT  PG,L'PG              print buffer
         LA     R6,1(R6)             i++
       ENDDO    ,                  enddo i
         L      R13,4(0,R13)       restore previous savearea pointer
         LM     R14,R12,12(R13)    restore previous context
         XR     R15,R15            rc=0
         BR     R14                exit
FIB      DS     32F                Fibonnacci table
BB       DS     X                  flag
PG       DS     CL80               buffer
XDEC     DS     CL12               temp
         YREGS
         END    ZECKEN