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

11l

Translation of: Python

V n = 20
F z(=n)
   I n == 0
      R [0]
   V fib = [2, 1]
   L fib[0] < n
      fib = [sum(fib[0.<2])] [+] fib
   [Int] dig
   L(f) fib
      I f <= n
         dig [+]= 1
         n -= f
      E
         dig [+]= 0
   R I dig[0] {dig} E dig[1..]

L(i) 0..n
   print(‘#3: #8’.format(i, z(i).map(d -> String(d)).join(‘’)))

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

360 Assembly

Translation of: BBC BASIC

*        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

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

Action!

PROC Encode(INT x CHAR ARRAY s)
  INT ARRAY fib(22)=
    [1 2 3 5 8 13 21 34 55 89 144 233 377 610
    987 1597 2584 4181 6765 10946 17711 28657]
  INT i
  BYTE append

  IF x=0 THEN
    s(0)=1
    s(1)='0
    RETURN
  FI

  i=21 append=0
  s(0)=0
  WHILE i>=0
  DO
    IF x>=fib(i) THEN
      x==-fib(i)
      s(0)==+1
      s(s(0))='1
      append=1
    ELSEIF append THEN
      s(0)==+1
      s(s(0))='0
    FI
    i==-1
  OD
RETURN

PROC Main()
  INT i
  CHAR ARRAY s(10)

  FOR i=0 TO 20
  DO
    Encode(i,s)
    PrintF("%I -> %S%E",i,s)
  OD
RETURN

Output:

Screenshot from Atari 8-bit computer

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

Ada

with Ada.Text_IO, Ada.Strings.Unbounded;

procedure Print_Zeck is
   
   function Zeck_Increment(Z: String) return String is
   begin
      if Z="" then 
	 return "1";
      elsif Z(Z'Last) = '1' then
	 return Zeck_Increment(Z(Z'First .. Z'Last-1)) & '0';
      elsif Z(Z'Last-1) = '0' then
	 return Z(Z'First .. Z'Last-1) & '1';
      else -- Z has at least two digits and ends with "10"
	 return Zeck_Increment(Z(Z'First .. Z'Last-2)) & "00";
      end if;
   end Zeck_Increment;
   
   use Ada.Strings.Unbounded;
   Current: Unbounded_String := Null_Unbounded_String;
   
begin
   for I in 1 .. 20 loop
      Current := To_Unbounded_String(Zeck_Increment(To_String(Current)));
      Ada.Text_IO.Put(To_String(Current) & " ");
   end loop;   
end Print_Zeck;

Output:

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

ALGOL 68

# print some Zeckendorf number representations                             #

# We handle 32-bit numbers, the maximum fibonacci number that can fit in a #
# 32 bit number is F(45)                                                   #

# build a table of 32-bit fibonacci numbers                                #
[ 45 ]INT fibonacci;
fibonacci[ 1 ] := 1;
fibonacci[ 2 ] := 2;
FOR i FROM 3 TO UPB fibonacci DO fibonacci[ i ] := fibonacci[ i - 1 ] + fibonacci[ i - 2 ] OD;

# returns the Zeckendorf representation of n or "?" if one cannot be found #
PROC to zeckendorf = ( INT n )STRING:
     IF n = 0 THEN
        "0"
     ELSE
        STRING result := "";
        INT    f pos  := UPB fibonacci;
        INT    rest   := ABS n;
        # find the first non-zero Zeckendorf digit                        #
        WHILE f pos > LWB fibonacci AND rest < fibonacci[ f pos ] DO
            f pos -:= 1
        OD;
        # if we found a digit, build the representation                   #
        IF f pos >= LWB fibonacci THEN
            # have a digit                                                #
            BOOL skip digit := FALSE;
            WHILE f pos >= LWB fibonacci DO
                IF   rest <= 0 THEN
                    result    +:= "0"
                ELIF skip digit THEN
                    # we used the previous digit                          #
                    skip digit := FALSE;
                    result    +:= "0"
                ELIF rest < fibonacci[ f pos ] THEN
                    # can't use the digit at f pos                        #
                    skip digit := FALSE;
                    result    +:= "0"
                ELSE
                    # can use this digit                                  #
                    skip digit := TRUE;
                    result    +:= "1";
                    rest      -:= fibonacci[ f pos ]
                FI;
                f pos -:= 1
            OD
        FI;
        IF rest = 0 THEN
            # found a representation                                      #
            result
        ELSE
            # can't find a representation                                 #
            "?"
        FI
     FI; # to zeckendorf #

FOR i FROM 0 TO 20 DO
    print( ( whole( i, -3 ), " ", to zeckendorf( i ), newline ) )
OD

Output:

AppleScript

Translation of: JavaScript

Translation of: Haskell

(mapAccumuL example)

--------------------- ZECKENDORF NUMBERS -------------------

-- zeckendorf :: Int -> String
on zeckendorf(n)
    script f
        on |λ|(n, x)
            if n < x then
                [n, 0]
            else
                [n - x, 1]
            end if
        end |λ|
    end script
    
    if n = 0 then
        {0} as string
    else
        item 2 of mapAccumL(f, n, |reverse|(just of tailMay(fibUntil(n)))) as string
    end if
end zeckendorf

-- fibUntil :: Int -> [Int]
on fibUntil(n)
    set xs to {}
    set limit to n
    
    script atLimit
        property ceiling : limit
        on |λ|(x)
            (item 2 of x) > (atLimit's ceiling)
        end |λ|
    end script
    
    script nextPair
        property series : xs
        on |λ|([a, b])
            set nextPair's series to nextPair's series & b
            [b, a + b]
        end |λ|
    end script
    
    |until|(atLimit, nextPair, {0, 1})
    return nextPair's series
end fibUntil

---------------------------- TEST --------------------------
on run
    
    intercalate(linefeed, ¬
        map(zeckendorf, enumFromTo(0, 20)))
    
end run

--------------------- GENERIC FUNCTIONS --------------------

-- enumFromTo :: Int -> Int -> [Int]
on enumFromTo(m, n)
    if m > n then
        set d to -1
    else
        set d to 1
    end if
    set lst to {}
    repeat with i from m to n by d
        set end of lst to i
    end repeat
    return lst
end enumFromTo

-- foldl :: (a -> b -> a) -> a -> [b] -> a
on foldl(f, startValue, xs)
    tell mReturn(f)
        set v to startValue
        set lng to length of xs
        repeat with i from 1 to lng
            set v to |λ|(v, item i of xs, i, xs)
        end repeat
        return v
    end tell
end foldl

-- 'The mapAccumL function behaves like a combination of map and foldl; 
-- it applies a function to each element of a list, passing an 
-- accumulating parameter from left to right, and returning a final 
-- value of this accumulator together with the new list.' (see Hoogle)

-- mapAccumL :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y])
on mapAccumL(f, acc, xs)
    script
        on |λ|(a, x)
            tell mReturn(f) to set pair to |λ|(item 1 of a, x)
            [item 1 of pair, (item 2 of a) & item 2 of pair]
        end |λ|
    end script
    
    foldl(result, [acc, []], xs)
end mapAccumL

-- map :: (a -> b) -> [a] -> [b]
on map(f, xs)
    tell mReturn(f)
        set lng to length of xs
        set lst to {}
        repeat with i from 1 to lng
            set end of lst to |λ|(item i of xs, i, xs)
        end repeat
        return lst
    end tell
end map

-- Lift 2nd class handler function into 1st class script wrapper 
-- mReturn :: Handler -> Script
on mReturn(f)
    if class of f is script then
        f
    else
        script
            property |λ| : f
        end script
    end if
end mReturn

-- intercalate :: Text -> [Text] -> Text
on intercalate(strText, lstText)
    set {dlm, my text item delimiters} to {my text item delimiters, strText}
    set strJoined to lstText as text
    set my text item delimiters to dlm
    return strJoined
end intercalate

-- reverse :: [a] -> [a]
on |reverse|(xs)
    if class of xs is text then
        (reverse of characters of xs) as text
    else
        reverse of xs
    end if
end |reverse|

-- tailMay :: [a] -> Maybe [a]
on tailMay(xs)
    if length of xs > 1 then
        {nothing:false, just:items 2 thru -1 of xs}
    else
        {nothing:true}
    end if
end tailMay

-- until :: (a -> Bool) -> (a -> a) -> a -> a
on |until|(p, f, x)
    set mp to mReturn(p)
    set v to x
    
    tell mReturn(f)
        repeat until mp's |λ|(v)
            set v to |λ|(v)
        end repeat
    end tell
    return v
end |until|

Output:

Arturo

Z: function [x][
    if x=0 -> return "0"
    fib: new [2 1]
    n: new x
    while -> n > first fib
          -> insert 'fib 0 fib\0 + fib\1
    
    result: new ""
    loop fib 'f [
        if? f =< n [
            'result ++ "1"
            'n - f
        ]
        else -> 'result ++ "0"
    ]
    if result\0 = `0` ->
        result: slice result 1 (size result)-1
    return result
]

loop 0..20 'i ->
    print [pad to :string i 3 pad Z i 8]

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

AutoHotkey

Works with: AutoHotkey_L

Fib := NStepSequence(1, 2, 2, 20)
Loop, 21 {
	i := A_Index - 1
	, Out .= i ":`t", n := ""
	Loop, % Fib.MaxIndex() {
		x := Fib.MaxIndex() + 1 - A_Index
		if (Fib[x] <= i)
			n .= 1, i -= Fib[x]
		else
			n .= 0
	}
	Out .= (n ? LTrim(n, "0") : 0) "`n"
}
MsgBox, % Out

NStepSequence(v1, v2, n, k) {
    a := [v1, v2]
	Loop, % k - 2 {
		a[j := A_Index + 2] := 0
		Loop, % j < n + 2 ? j - 1 : n
			a[j] += a[j - A_Index]
	}
	return, a
}

NStepSequence()

Output:

AutoIt

For $i = 0 To 20
	ConsoleWrite($i &": "& Zeckendorf($i)&@CRLF)
Next

Func Zeckendorf($int, $Fibarray = "")
	If Not IsArray($Fibarray) Then $Fibarray = Fibonacci($int)
	Local $ret = ""
	For $i = UBound($Fibarray) - 1 To 1 Step -1
		If $Fibarray[$i] > $int And $ret = "" Then ContinueLoop ; dont use Leading  Zeros
		If $Fibarray[$i] > $int Then
			$ret &= "0"
		Else
			If StringRight($ret, 1) <>  "1" Then
				$ret &= "1"
				$int -= $Fibarray[$i]
			Else
				$ret &= "0"
			EndIf
		EndIf
	Next
	If $ret = "" Then $ret = "0"
	Return $ret
EndFunc   ;==>Zeckendorf

Func Fibonacci($max)
	$AList = ObjCreate("System.Collections.ArrayList")
	$AList.add("0")
	$current = 0
	While True
		If $current > 1 Then
			$count = $AList.Count
			$current = $AList.Item($count - 1)
			$current = $current + $AList.Item($count - 2)
		Else
			$current += 1
		EndIf
		$AList.add($current)
		If $current > $max Then ExitLoop
	WEnd
	$Array = $AList.ToArray
	Return $Array
EndFunc   ;==>Fibonacci

Output:

BASIC

BBC BASIC

      FOR n% = 0 TO 20
        PRINT n% RIGHT$("       " + FNzeckendorf(n%), 8)
      NEXT
      PRINT '"Checking numbers up to 10000..."
      FOR n% = 21 TO 10000
        IF INSTR(FNzeckendorf(n%), "11") STOP
      NEXT
      PRINT "No Zeckendorf numbers contain consecutive 1's"
      END
      
      DEF FNzeckendorf(n%)
      LOCAL i%, o$, fib%() : DIM fib%(45)
      fib%(0) = 1 : fib%(1) = 1 : i% = 1
      REPEAT
        i% += 1
        fib%(i%) = fib%(i%-1) + fib%(i%-2)
      UNTIL fib%(i%) > n%
      REPEAT
        i% -= 1
        IF n% >= fib%(i%) THEN
          o$ += "1"
          n% -= fib%(i%)
        ELSE
          o$ += "0"
        ENDIF
      UNTIL i% = 1
      = o$

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

Checking numbers up to 10000...
No Zeckendorf numbers contain consecutive 1's

FreeBASIC

' version 17-10-2016
' compile with: fbc -s console

#Define max 92 ' max for Fibonacci number

Dim Shared As ULongInt fib(max)

fib(0) = 1
fib(1) = 1

For x As Integer = 2 To max
  fib(x) = fib(x-1) + fib(x-2)
Next

Function num2zeck(n As Integer) As String

If n < 0 Then
  Print "Error: no negative numbers allowed"
  Beep : Sleep 5000,1 : End
End If

If n < 2 Then Return Str(n)

  Dim As String zeckendorf
  
  For x As Integer = max To 1 Step -1
    If fib(x) <= n Then
      zeckendorf = zeckendorf + "1"
      n = n - fib(x)
    Else
      zeckendorf = zeckendorf + "0"
    End If
  Next

  return LTrim(zeckendorf, "0") ' get rid of leading zeroes
End Function

' ------=< MAIN >=------

Dim As Integer x, e
Dim As String zeckendorf
Print "number       zeckendorf"

For x = 0 To 200000
  
  zeckendorf = num2zeck(x)
  If x <= 20 Then Print x, zeckendorf
  
  ' check for two consecutive Fibonacci numbers
  If InStr(zeckendorf, "11") <> 0 Then
    Print " Error: two consecutive Fibonacci numbers "; x, zeckendorf
    e = e +1
  End If
Next

Print
If e = 0 Then
  Print " No Zeckendorf numbers with two consecutive Fibonacci numbers found"
Else
  Print e; " error(s) found"
End If

' empty keyboard buffer
While Inkey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End

Output:

number       zeckendorf
 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

 No Zeckendorf numbers with two consecutive Fibonacci numbers found

Liberty BASIC

CBTJD: 2020/03/09

Works with: Just BASIC

samples = 20
call zecklist samples

print "Decimal","Zeckendorf"
for n = 0 to samples
  print n, zecklist$(n)
next n

Sub zecklist inDEC
  dim zecklist$(inDEC)
  do
    bin$ = dec2bin$(count)
    if instr(bin$,"11") = 0 then
      zecklist$(found) = bin$
      found = found + 1
    end if
    count = count+1
  loop until found = inDEC + 1
End sub

function dec2bin$(inDEC)
  do
    bin$ = str$(inDEC mod 2) + bin$
    inDEC = int(inDEC/2)
  loop until inDEC = 0
  dec2bin$ = bin$
end function

Output:

Decimal       Zeckendorf
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

PureBasic

Procedure.s zeck(n.i)
  Dim f.i(1) : Define i.i=1, o$
  f(0)=1 : f(1)=1 
  While f(i)<n 
    i+1 : ReDim f(ArraySize(f())+1) : f(i)=f(i-1)+f(i-2) 
  Wend
  For i=i To 1 Step -1    
    If n>=f(i) : o$+"1" : n-f(i) : Else : o$+"0" : EndIf
  Next
  If Len(o$)>1 : o$=LTrim(o$,"0") : EndIf
  ProcedureReturn o$
EndProcedure

Define n.i, t$
OpenConsole("Zeckendorf number representation")
PrintN(~"\tNr.\tZeckendorf")
For n=0 To 20
  t$=zeck(n)  
  If FindString(t$,"11")
    PrintN("Error: n= "+Str(n)+~"\tZeckendorf= "+t$)
    Break
  Else
    PrintN(~"\t"+RSet(Str(n),3," ")+~"\t"+RSet(t$,7," "))    
  EndIf
Next
Input()

Output:

        Nr.     Zeckendorf
          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

QuickBASIC

Translation of: ALGOL 68

' Zeckendorf number representation
DECLARE FUNCTION ToZeckendorf$ (N%)
' The maximum Fibonacci number that can fit in a
' 32 bit number is Fib&(45)                                              
CONST MAXFIBINDEX% = 45, TRUE% = -1, FALSE% = 0
DIM SHARED Fib&(1 TO MAXFIBINDEX%)
Fib&(1) = 1: Fib&(2) = 2
FOR I% = 3 TO MAXFIBINDEX%
  Fib&(I%) = Fib&(I% - 1) + Fib&(I% - 2)
NEXT I%
FOR I% = 0 TO 20
  SixChars$ = SPACE$(6)
  RSET SixChars$ = ToZeckendorf$(I%)
  PRINT USING "### "; I%; : PRINT SixChars$
NEXT I%
END

FUNCTION ToZeckendorf$ (N%)
  ' returns the Zeckendorf representation of N% or "?" if one cannot be found
  IF N% = 0 THEN
    ToZeckendorf$ = "0"
  ELSE
    Result$ = ""
    FPos% = MAXFIBINDEX%
    Rest% = ABS(N%)
    ' Find the first non-zero Zeckendorf digit
    WHILE FPos% > 1 AND Rest% < Fib&(FPos%)
      FPos% = FPos% - 1
    WEND
    ' If we found a digit, build the representation
    IF FPos% >= 1 THEN ' have a digit
      SkipDigit% = FALSE%
      WHILE FPos% >= 1
        IF Rest% <= 0 THEN
          Result$ = Result$ + "0"
        ELSEIF SkipDigit% THEN ' we used the previous digit
          SkipDigit% = FALSE%
          Result$ = Result$ + "0"
        ELSEIF Rest% < Fib&(FPos%) THEN ' cannot use the digit at FPos%
          SkipDigit% = FALSE%
          Result$ = Result$ + "0"
        ELSE ' can use this digit
          SkipDigit% = TRUE%
          Result$ = Result$ + "1"
          Rest% = Rest% - Fib&(FPos%)
        END IF
        FPos% = FPos% - 1
      WEND
    END IF
    IF Rest% = 0 THEN
      ToZeckendorf$ = Result$
    ELSE
      ToZeckendorf$ = "?"
    END IF
  END IF
END FUNCTION

Output:

Sinclair ZX81 BASIC

Works on the 1k RAM model, albeit without much room for manoeuvre. (You'd like the Zeckendorf numbers further over towards the right-hand side of the screen? Sorry, can't spare the video RAM.) If you have 2k or more, you can replace the constant 6 with some higher value wherever it occurs in the program and enable yourself to represent bigger numbers in Zeckendorf form.

 10 DIM F(6)
 20 LET F(1)=1
 30 LET F(2)=2
 40 FOR I=3 TO 6
 50 LET F(I)=F(I-2)+F(I-1)
 60 NEXT I
 70 FOR I=0 TO 20
 80 LET Z$=""
 90 LET S$=" "
100 LET Z=I
110 FOR J=6 TO 1 STEP -1
120 IF J=1 THEN LET S$="0"
130 IF Z<F(J) THEN GOTO 180
140 LET Z$=Z$+"1"
150 LET Z=Z-F(J)
160 LET S$="0"
170 GOTO 190
180 LET Z$=Z$+S$
190 NEXT J
200 PRINT I;" ";
210 IF I<10 THEN PRINT " ";
220 PRINT Z$
230 NEXT I

Output:

uBasic/4tH

For x = 0 to 20                        ' Print Zeckendorf numbers 0 - 20
  Print x,
  Push x : Gosub _Zeckendorf           ' get Zeckendorf number repres.
  Print                                ' terminate line
Next

End

_Fibonacci
  Push Tos()                           ' duplicate TOS()
  @(0) = 0                             ' This function returns the
  @(1) = 1                             ' Fibonacci number which is smaller
                                       ' or equal to TOS()
  Do While @(1) < Tos() + 1
     Push (@(1))
     @(1) = @(0) + @(1)                ' get next Fibonacci number
     @(0) = Pop()
  Loop                                 ' loop if not exceeded TOS()

  Gosub _Drop                          ' clear TOS()
  Push @(0)                            ' return Fibonacci number
Return

_Zeckendorf
  GoSub _Fibonacci                     ' This function breaks TOS() up
  Print Tos();                         ' into its Zeckendorf components
  Push -(Pop() - Pop())                ' first digit is always there
                                       ' the remainder to resolve
  Do While Tos()                       ' now go for the next digits
    GoSub _Fibonacci
    Print " + ";Tos();                 ' print the next digit
    Push -(Pop() - Pop())
  Loop

  Gosub _Drop                          ' clear TOS()
Return                                 ' and return

_Drop
  If Pop()%1 = 0 Then Return           ' This function clears TOS()

Output:

0       0
1       1
2       2
3       3
4       3 + 1
5       5
6       5 + 1
7       5 + 2
8       8
9       8 + 1
10      8 + 2
11      8 + 3
12      8 + 3 + 1
13      13
14      13 + 1
15      13 + 2
16      13 + 3
17      13 + 3 + 1
18      13 + 5
19      13 + 5 + 1
20      13 + 5 + 2

0 OK, 0:901

VBA

Translation of: Phix

Private Function zeckendorf(ByVal n As Integer) As Integer
    Dim r As Integer: r = 0
    Dim c As Integer
    Dim fib As New Collection
    fib.Add 1
    fib.Add 1
    Do While fib(fib.Count) < n
        fib.Add fib(fib.Count - 1) + fib(fib.Count)
    Loop
    For i = fib.Count To 2 Step -1
        c = n >= fib(i)
        r = r + r - c
        n = n + c * fib(i)
    Next i
    zeckendorf = r
End Function
 
Public Sub main()
    Dim i As Integer
    For i = 0 To 20
        Debug.Print Format(i, "@@"); ":"; Format(WorksheetFunction.Dec2Bin(zeckendorf(i)), "@@@@@@@")
    Next i
End Sub

Output:

VBScript

Function Zeckendorf(n)
	num = n
	Set fibonacci = CreateObject("System.Collections.Arraylist")
	fibonacci.Add 1 : fibonacci.Add 2
	i = 1
	Do While fibonacci(i) < num
		fibonacci.Add fibonacci(i) + fibonacci(i-1)
		i = i + 1
	Loop
	tmp = ""
	For j = fibonacci.Count-1 To 0 Step -1
		If fibonacci(j) <= num And (tmp = "" Or Left(tmp,1) <> "1") Then
			tmp = tmp & "1"
			num = num - fibonacci(j)
		Else
			tmp = tmp & "0"
		End If
	Next
	Zeckendorf = CLng(tmp)
End Function

'testing the function
For k = 0 To 20
	WScript.StdOut.WriteLine k & ": " & Zeckendorf(k)
Next

Output:

Yabasic

sub Zeckendorf(n)
	local i, n$, c
	
	do
		n$ = bin$(i)
		if not instr(n$,"11") then
			print c,":\t",n$
			if c = n break
			c = c + 1			
		end if
		i = i + 1
	loop
end sub

Zeckendorf(20)

bc

obase = 2
f[0] = 1
f[t = 1] = 2

define z(n) {
        auto p, r

        for (p = t; p >= 0; --p) {
                r += r
                if (n >= f[p]) {
                        r += 1
                        n -= f[p]
                }
        }
        return(r)
}

for (x = 0; x != 21; ++x) {
        if (x > f[t]) {
                t += 1
                f[t] = f[t - 2] + f[t - 1]
        }
        z(x)
}

Output:

Befunge

The first number on the stack, 45*, specifies the range of values to display. However, the algorithm depends on a hardcoded list of Fibonacci values (currently just 10) so the theoretical maximum is 143. It's also constrained by the range of a Befunge data cell, which on many implementations will be as low as 127.

45*83p0>:::.0`"0"v
v53210p 39+!:,,9+<
>858+37 *66g"7Y":v
>3g`#@_^   v\g39$<
^8:+1,+5_5<>-:0\`|
v:-\g39_^#:<*:p39<
>0\`:!"0"+#^ ,#$_^

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

C

#include <stdio.h>

typedef unsigned long long u64;

#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;
}

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

C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Zeckendorf
{
    class Program
    {
        private static uint Fibonacci(uint n)
        {
            if (n < 2)
            {
                return n;
            }
            else
            {
                return Fibonacci(n - 1) + Fibonacci(n - 2);
            }
        }

        private static string Zeckendorf(uint num)
        {
            IList<uint> fibonacciNumbers = new List<uint>();
            uint fibPosition = 2;

            uint currentFibonaciNum = Fibonacci(fibPosition);

            do
            {
                fibonacciNumbers.Add(currentFibonaciNum);
                currentFibonaciNum = Fibonacci(++fibPosition);
            } while (currentFibonaciNum <= num);

            uint temp = num;
            StringBuilder output = new StringBuilder();

            foreach (uint item in fibonacciNumbers.Reverse())
            {
                if (item <= temp)
                {
                    output.Append("1");
                    temp -= item;
                }
                else
                {
                    output.Append("0");
                }
            }

            return output.ToString();
        }

        static void Main(string[] args)
        {
            for (uint i = 1; i <= 20; i++)
            {
                string zeckendorfRepresentation = Zeckendorf(i);
                Console.WriteLine(string.Format("{0} : {1}", i, zeckendorfRepresentation));
            }

            Console.ReadKey();
        }
    }
}

Output:

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

C++

Using a C++11 User Defined Literal

Works with: C++11

see Here for a further example using this class.

// For a class N which implements Zeckendorf numbers:
// I define an increment operation ++()
// I define a comparison operation <=(other N)
// Nigel Galloway October 22nd., 2012
#include <iostream>
class N {
private:
  int dVal = 0, dLen;
public:
  N(char const* x = "0"){
    int i = 0, q = 1;
    for (; x[i] > 0; i++);
    for (dLen = --i/2; i >= 0; i--) {
      dVal+=(x[i]-48)*q;
      q*=2;
  }}
  const N& operator++() {
    for (int i = 0;;i++) {
      if (dLen < i) dLen = i;
      switch ((dVal >> (i*2)) & 3) {
        case 0: dVal += (1 << (i*2)); return *this;
        case 1: dVal += (1 << (i*2)); if (((dVal >> ((i+1)*2)) & 1) != 1) return *this;
        case 2: dVal &= ~(3 << (i*2));
  }}}
  const bool operator<=(const N& other) const {return dVal <= other.dVal;}
  friend std::ostream& operator<<(std::ostream&, const N&);
};
N operator "" N(char const* x) {return N(x);}
std::ostream &operator<<(std::ostream &os, const N &G) {
  const static std::string dig[] {"00","01","10"}, dig1[] {"","1","10"};
  if (G.dVal == 0) return os << "0";
  os << dig1[(G.dVal >> (G.dLen*2)) & 3];
  for (int i = G.dLen-1; i >= 0; i--) os << dig[(G.dVal >> (i*2)) & 3];
  return os;
}

I may now write:

int main(void) {
//for (N G; G <= 101010N; ++G) std::cout << G << std::endl;       // from zero to 101010M
  for (N G(101N); G <= 101010N; ++G) std::cout << G << std::endl; // from 101N to 101010N
  return 0;
}

Which produces:

Output:

Clojure

(def fibs (lazy-cat [1 1] (map + fibs (rest fibs))))

(defn z [n]
  (if (zero? n)
    "0"
    (let [ps (->> fibs (take-while #(<= % n)) rest reverse)
          fz (fn [[s n] p]
                (if (>= n p)
                  [(conj s 1) (- n p)]
                  [(conj s 0) n]))]
      (->> ps (reduce fz [[] n]) first (apply str)))))

(doseq [n (range 0 21)] (println n (z n)))

CLU

% Get list of distinct Fibonacci numbers up to N
fibonacci = proc (n: int) returns (array[int])
    list: array[int] := array[int]$[]
    a: int := 1
    b: int := 2
    while a <= n do
        array[int]$addh(list,a)
        a, b := b, a+b
    end
    return(list)
end fibonacci
    
% Find the Zeckendorf representation of N
zeckendorf = proc (n: int) returns (string) signals (negative)
    if n<0 then signal negative end
    if n=0 then return("0") end
    
    fibs: array[int] := fibonacci(n)
    result: array[char] := array[char]$[]
    
    while ~array[int]$empty(fibs) do
        fib: int := array[int]$remh(fibs)
        if fib <= n then
            n := n - fib
            array[char]$addh(result,'1')
        else
            array[char]$addh(result,'0')
        end
    end
    return(string$ac2s(result))
end zeckendorf

% Print the Zeckendorf representations of 0 to 20
start_up = proc ()
    po: stream := stream$primary_output()
    for i: int in int$from_to(0,20) do
        stream$putright(po, int$unparse(i), 2)
        stream$puts(po, ": ")
        stream$putl(po, zeckendorf(i))
    end
end start_up

Output:

Common Lisp

Common Lisp's arbitrary precision integers should handle any positive input:

(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)))

;; 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 "~%"))))))

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

Cowgol

include "cowgol.coh";

sub zeckendorf(n: uint32, buf: [uint8]): (r: [uint8]) is
    var fibs: uint32[] := {
        0,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,2971215073
    };
    r := buf;
    if n == 0 then
        [r] := '0';
        [@next r] := 0;
        return;
    end if;
    
    var fib: [uint32] := &fibs[1];
    while n >= [fib] loop 
        fib := @next fib; 
    end loop;
    fib := @prev fib;
    
    while [fib] != 0 loop
        if [fib] <= n then
            n := n - [fib];
            [buf] := '1';
        else
            [buf] := '0';
        end if;
        fib := @prev fib;
        buf := @next buf;
    end loop;
    [buf] := 0;
end sub;

var i: uint32 := 0;
while i <= 20 loop
    print_i32(i);
    print(": ");
    print(zeckendorf(i, LOMEM));
    print_nl();
    i := i + 1;
end loop;

Output:

Crystal

Translation of: Ruby of Python

def zeckendorf(n)
  return 0 if n.zero?
  fib = [1, 2]
  while fib[-1] < n; fib << fib[-2] + fib[-1] end
  digit = ""
  fib.reverse_each do |f|
    if f <= n
      digit, n = digit + "1", n - f
    else
      digit += "0"
    end
  end
  digit.to_i
end
 
(0..20).each { |i| puts "%3d: %8d" % [i, zeckendorf(i)] }

Using an explicit Iterator.

class ZeckendorfIterator
  include Iterator(String)

  def initialize
    @x = 0
  end

  def next
    bin = @x.to_s(2)
    @x += 1
    while bin.includes?("11")
      bin = @x.to_s(2)
      @x += 1
    end
    bin
  end
end

def zeckendorf(n)
  ZeckendorfIterator.new.first(n)
end

zeckendorf(21).each_with_index{ |x,i| puts "%3d: %8s"% [i, x] }

Using oneliners.

def zeckendorf(n)
  0.step.map(&.to_s(2)).reject(&.includes?("11")).first(n)
end

# or a little faster

def zeckendorf(n)
  0.step.compact_map{ |x| bin = x.to_s(2); bin unless bin.includes?("11") }.first(n)
end

zeckendorf(21).each_with_index{ |x,i| puts "%3d: %8s"% [i, x] }

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

D

Translation of: Haskell

import std.stdio, std.range, std.algorithm, std.functional;

void main() {
    size_t
    .max
    .iota
    .filter!q{ !(a & (a >> 1)) }
    .take(21)
    .binaryReverseArgs!writefln("%(%b\n%)");
}

Output:

Translation of: Go

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));
}

Output:

Translation of: Tcl

(Same output.)

import std.stdio, std.algorithm, std.range;

string zeckendorf(size_t n) {
    if (n == 0)
        return "0";
    auto fibs = recurrence!q{a[n - 1] + a[n - 2]}(1, 2);

    string result;
    foreach_reverse (immutable f; fibs.until!(x => x > n).array) {
        result ~= (f <= n) ? '1' : '0';
        if (f <= n)
            n -= f;
    }

    return result;
}

void main() {
    foreach (immutable i; 0 .. 21)
        writefln("%2d: %6s", i, i.zeckendorf);
}

Dart

Translation of: Java

class Zeckendorf {
  static String getZeckendorf(int n) {
    if (n == 0) {
      return "0";
    }
    List<int> fibNumbers = [1];
    int nextFib = 2;
    while (nextFib <= n) {
      fibNumbers.add(nextFib);
      nextFib += fibNumbers[fibNumbers.length - 2];
    }
    StringBuffer sb = StringBuffer();
    for (int i = fibNumbers.length - 1; i >= 0; i--) {
      int fibNumber = fibNumbers[i];
      sb.write((fibNumber <= n) ? "1" : "0");
      if (fibNumber <= n) {
        n -= fibNumber;
      }
    }
    return sb.toString();
  }

  static void main() {
    for (int i = 0; i <= 20; i++) {
      print("Z($i)=${getZeckendorf(i)}");
    }
  }
}

void main() {
  Zeckendorf.main();
}

Output:

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

Delphi

Works with: Delphi version 6.0

Library: SysUtils,StdCtrls

const FibNums: array [0..21] of integer =
      (1, 2, 3, 5, 8, 13, 21, 34, 55, 89,
       144, 233, 377, 610, 987, 1597, 2584,
       4181, 6765, 10946, 17711, 28657);


function GetZeckNumber(N: integer): string;
{Returns Zeckendorf number for N as string}
var I: integer;
begin
Result:='';
{Subtract Fibonacci numbers from N}
for I:=High(FibNums) downto 0 do
 if (N-FibNums[I])>=0 then
	begin
	Result:=Result+'1';
	N:=N-FibNums[I];
	end
 else if Length(Result)>0 then Result:=Result+'0';
if Result='' then Result:='0';
end;


procedure ShowZeckendorfNumbers(Memo: TMemo);
var I: integer;
var S: string;
begin
S:='';
for I:=0 to 20 do
	begin
	Memo.Lines.Add(IntToStr(I)+': '+GetZeckNumber(I));
	end;
end;

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

Elapsed Time: 26.683 ms.

EasyLang

Translation of: FreeBASIC

proc mkfibs n . fib[] .
   fib[] = [ ]
   last = 1
   current = 1
   while current <= n
      fib[] &= current
      nxt = last + current
      last = current
      current = nxt
   .
.
func$ zeckendorf n .
   mkfibs n fib[]
   for pos = len fib[] downto 1
      if n >= fib[pos]
         zeck$ &= "1"
         n -= fib[pos]
      else
         zeck$ &= "0"
      .
   .
   if zeck$ = ""
      return "0"
   .
   return zeck$
.
for n = 0 to 20
   print " " & n & " " & zeckendorf n
.

EchoLisp

We analytically find the first fibonacci(i) >= n, using the formula i = log((n* Φ) + 0.5) / log(Φ) .

;; special fib's starting with 1 2 3 5 ...
(define (fibonacci n)
    (+ (fibonacci (1- n)) (fibonacci (- n 2))))
(remember 'fibonacci #(1 2))

(define-constant Φ (// (1+ (sqrt 5)) 2))
(define-constant logΦ (log Φ))
;; find i : fib(i) >= n
(define (iFib n)
   (floor (// (log (+ (* n Φ) 0.5)) logΦ)))
    
;; left trim zeroes
(string-delimiter "")
(define (zeck->string digits)
        (if (!= 0 (first digits)) 
            (string-join digits "") 
            (zeck->string (rest digits))))
    
(define (Zeck n)
        (cond
        (( < n 0) "no negative zeck")
        ((inexact? n) "no floating zeck")
        ((zero? n) "0")
        (else (zeck->string
                (for/list ((s (reverse (take fibonacci (iFib n)))))
                (if ( > s n) 0 
                    (begin (-= n s) 1 )))))))

Output:

(take Zeck 21)
    → (0 1 10 100 101 1000 1001 1010 10000 10001 
     10010 10100 10101 100000 100001 100010 100100 100101 101000 101001 101010)

(Zeck 1000000000)
    → 1010000100100001010101000001000101000101001

Elena

Translation of: C#

ELENA 6.x :

import system'routines;
import system'collections;
import system'text;
import extensions;
extension op
{
    fibonacci()
    {
        if (self < 2)
        { 
            ^ self
        }
        else
        {
            ^ (self - 1).fibonacci() + (self - 2).fibonacci()
        };
    }
    
    zeckendorf()
    {
        var fibonacciNumbers := new List<int>();
        
        int num := self;
        int fibPosition := 2;
        int currentFibonaciNum := fibPosition.fibonacci();
        
        while (currentFibonaciNum <= num)
        {
            fibonacciNumbers.append(currentFibonaciNum);
            
            fibPosition := fibPosition + 1;
            currentFibonaciNum := fibPosition.fibonacci()
        };
        
        auto output := new TextBuilder();
        int temp := num;
        
        fibonacciNumbers.sequenceReverse().forEach::(item)
        {
            if (item <= temp)
            {
                output.write("1");
                temp := temp - item
            }
            else
            {
                output.write("0")
            }
        };
        
        ^ output.Value
    }
}
                
public program()
{
    for(int i := 1; i <= 20; i += 1)
    {
        console.printFormatted("{0} : {1}",i,i.zeckendorf()).writeLine()
    };
    
    console.readChar()
}

Output:

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

Elixir

Translation of: Ruby

Stream generator:

defmodule Zeckendorf do
  def number do
    Stream.unfold(0, fn n -> zn_loop(n) end)
  end
  
  defp zn_loop(n) do
    bin = Integer.to_string(n, 2)
    if String.match?(bin, ~r/11/), do: zn_loop(n+1), else: {bin, n+1}
  end
end

Zeckendorf.number |> Enum.take(21) |> Enum.with_index
|> Enum.each(fn {zn, i} -> IO.puts "#{i}: #{zn}" end)

Output:

Fibonacci numbers:

defmodule Zeckendorf do
  def number(n) do
    fib_loop(n, [2,1])
    |> Enum.reduce({"",n}, fn f,{dig,i} ->
         if f <= i, do: {dig<>"1", i-f}, else: {dig<>"0", i}
       end)
    |> elem(0) |> String.to_integer
  end
  
  defp fib_loop(n, fib) when n < hd(fib), do: fib
  defp fib_loop(n, [a,b|_]=fib), do: fib_loop(n, [a+b | fib])
end

for i <- 0..20, do: IO.puts "#{i}: #{Zeckendorf.number(i)}"

same output

Erlang

Translation of: Elixir

% Function to generate a list of the first N Zeckendorf numbers
number(N) ->
    number_helper(N, 0, 0, []).

number_helper(0, _, _, Acc) ->
    lists:reverse(Acc);
number_helper(N, Curr, Index, Acc) ->
    case zn_loop(Curr) of
        {Bin, Next} ->
            number_helper(N - 1, Next, Index + 1, [{Bin, Index} | Acc])
    end.

% Helper function to find the next Zeckendorf number
zn_loop(N) ->
    Bin = my_integer_to_binary(N),
    case re:run(Bin, "11", [{capture, none}]) of
        match ->
            zn_loop(N + 1);
        nomatch ->
            {Bin, N + 1}
    end.

% Convert an integer to its binary representation as a string
my_integer_to_binary(N) ->
    lists:flatten(io_lib:format("~.2B", [N])).

% Test function to output the first 21 Zeckendorf numbers
main([]) ->
    ZnNumbers = number(21),
    lists:foreach(
        fun({Zn, I}) ->
            io:format("~p: ~s~n", [I, Zn])
        end, ZnNumbers).

Output:

F#

let fib = Seq.unfold (fun (x, y) -> Some(x, (y, x + y))) (1,2)

let zeckendorf n =
    if n = 0 then ["0"]
    else
        let folder k state =
            let (n, z) = (fst state), (snd state)
            if n >= k then (n - k, "1" :: z)
            else (n, "0" :: z)
        let fb = fib |> Seq.takeWhile (fun i -> i<=n) |> Seq.toList
        snd (List.foldBack folder fb (n, []))
        |> List.rev

for i in 0 .. 20 do printfn "%2d: %8s" i (String.concat "" (zeckendorf i))

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

Factor

USING: formatting kernel locals make math sequences ;

:: fib<= ( n -- seq )
    1 2 [ [ dup n <= ] [ 2dup + [ , ] 2dip ] while drop , ]
    { } make ;
    
:: zeck ( n -- str )
    0 :> s! n fib<= <reversed>
    [ dup s + n <= [ s + s! 49 ] [ drop 48 ] if ] "" map-as ;
    
21 <iota> [ dup zeck "%2d: %6s\n" printf ] each

Output:

Forth

: fib<= ( n -- n )
    >r 0 1 BEGIN dup r@ <= WHILE  tuck +  REPEAT  drop rdrop ;

: z. ( n -- )
   dup fib<= dup . -
   BEGIN ?dup WHILE
      dup fib<= dup [char] + emit space . -
   REPEAT ;

: tab  9 emit ;

: zeckendorf ( -- )
    21 0 DO
        cr i 2 .r tab i z.
    LOOP ;

Output:

zeckendorf
 0	0
 1	1
 2	2
 3	3
 4	3 + 1
 5	5
 6	5 + 1
 7	5 + 2
 8	8
 9	8 + 1
10	8 + 2
11	8 + 3
12	8 + 3 + 1
13	13
14	13 + 1
15	13 + 2
16	13 + 3
17	13 + 3 + 1
18	13 + 5
19	13 + 5 + 1
20	13 + 5 + 2  ok

Fortran

The simplest representation of a number in the Zeckendorf manner is as a sequence of digits, such as are used in multi-precision arithmetic, and for this an array of integers will do. Rather excessively, as only two states are required and the default integer style is usually thirty-two bits these days. Some compilers allow the specification of one-byte integers, as in INTEGER*1 D(0:ZLAST) so that would be only an eight-fold excess. One could escalate to fiddling with individual bits within a number (as is done in Extensible_prime_generator#Fortran) and a 16-bit integer would be adequate for the specified tests, but Fortran syntax has not been extended to offer simple methods for manipulating bits such as D(7:7) to obtain the seventh bit of D. Instead one might use special library routines as supplied by F90 such as IBITS(D,7,1) for the same effect, though possibly at a cost in code size and execution time. Less storage may be saved through cramming bits than is consumed by the code needed to extract individual bits. Such values could then be displayed using theB format code. However, the source code would now be littered with the details of bit access rather than the form of the Zeckendorf procedure.

An alternative lies in noting that only the sequences 00, 01, and 10 can appear (because 11 is unnecessary; see below), so a base three scheme could be used to represent the three such pairs of bits. But this still contains redundancies. Suppose a 01 value is somewhere in the sequence: then it may be followed only by 00 or 01, and likewise 10 be preceded only by 10 or 00; just two values, not three. Perhaps a still more cunning compaction scheme could be devised to take advantage of these details, or some other scheme concocted. For simplicity, no compaction will be attempted so the states of 0 and 1 will be represented by a simple integer devoted to that bit.

The conversion scheme requires the values of the Fibonacci sequence, except not quite: the Fibonacci sequence starts F₀ = 0, F₁ = 1, F₂ = 1, F₃ = 2, F₄ = 3, etc. but what is wanted is to start with the second 1, so F₁ = 1, F₂ = 2, F₃ = 3, F₄ = 5, etc. so this sequence has been named the Fib1nacci sequence to replace conceptual dissonance with lexical dissonance, and similarly with array F1B instead of FIB. Initial investigations show that F₄₅ is the last before a thirty-two bit two's complement integer is overflowed, though systems offering INTEGER*8 could be pushed further.

Initialising this table in array F1B could be done via specifying the relevant values (computed separately, even by hand) or by some banal initialisation loop that would be executed on the first invocation of any of the routines requiring those values, a tedious and annoying rigmarole to organise. More interesting are the facilities offered by the PARAMETER statement (introduced with F77), with the further possibility that constants, so defined, would be held safe from accidental change, nor would there be initialising code to execute at run time. Alas, the obvious approach (commented out in the source) using array F1B is rejected by the F90 compiler even though it does allow a value to be defined in terms of other defined values, as is demonstrated by the horde of simple variables following. Despite being a multi-pass compiler, the dependencies will not be unravelled if the statements appear out of order. Fortran does not include a standard pre-processor stage, unlike say pl/i where it is built-in to the language and uses much the same syntax as normal pl/i statements, so loops, IF-tests and so forth are available. By such means, the upper limit of 45 could be determined, the initial values calculated, and the array be defined with initial values, all at compile time.

By declaring the horde of simple names to have the PRIVATE attribute, they will not litter the name space of routines invoking the module, but alas, they will still occupy their own storage space. Another possibility would be to use the EQUIVALENCE statement to have them placed within array F1B, but alas, as noted in 15_Puzzle_Game#Fortran, the compiler will not countenance PARAMETER statements for names engaged in such misbehviour. A pity.

Still another possibility would be to take advantage of the formula for calculating the values of the Fibonacci series directly (with careful attention to the offsets needed for the Fib1nacci sequence), but this formula is rather intimidating:

F(N) = ((1 + SQRT(5))**N - (1 - SQRT(5))**N)/(SQRT(5)*2**N)

It can easily be coded as a Fortran function (and would have to be double precision because 32-bit floating-point arithmetic is not accurate enough for integer constants approaching 32 bits), but alas, the compiler does not allow itself to take the risk of invoking a user-written function in a PARAMETER statement, even if the compiler had itself compiled it. For, who knows what it might do?

Given the array F1B the conversion from an integer to Zeckendorf digit sequence starts from the high-order end to find the highest F1B value not exceeding the number. There is a formula for this mentioned in the EchoLisp section, but it too is intimidating and the rounding of its result would also require checking. Rather than a linear search, a binary chop could be used, though at the cost of additional code. The location of the high-order digit is recorded on general principles, it being useful in formatting output for example. This requires a "first-time" test within the loop, that could be avoided if the conversion were to be done in two stages.

The special feature of the conversion lies in noting that F1B(n + 1) = F1B(n) + F1B(n - 1), the defining feature of the Fibonacci sequence. Thus, when a 1-bit is found (say it is bit n), the next bit down must be a 0 and so the test for it may be skipped, by incrementing L This is because if it were not 0, then the bit above (bit n + 1) would have been turned on in the previous stage instead. Because of this adjustment, the controlling loop cannot be DO L = ZLAST,1,-1 to step down the entries in array F1B because modifications to the index variable of a DO-loop, if not rejected out-of-hand by the compiler, may have no effect on the execution of the loop. This is because the execution of a DO-loop is often controlled by an "iteration count", calculated on entry to the DO-loop, which is thereby unaffected by changes to the index variable, or indeed to the bounds and step size of the loop. Other implementations of a DO-loop will offer other behaviour. There being no equivalent in Fortran of Repeat ... until ... ; (whereby the test is at the end, and there is no initial test), a GO TO appears...

The source uses F90 for its MODULE facility, in particular having array F1B available without having to mess about with additional parameters or COMMON statements. This also enables the specification of arrays with a lower bound other than one, which makes it easy to define the digit arrays to have a current length, stored in element zero. This sort of "string" facility is often restricted only to strings of characters, but the notion "string of <type>" is often useful. If in routines declared within a MODULE the size of an array parameter is declared via : there are secret additional parameters defining its size, accessible via special functions such as UBOUND so there is no need for an explicit parameter doing so as would be the case prior to F90. With F90 it is also possible to define a compound data type for the digit sequence, but a simple array seems more flexible.

The pleasing name, "MODULE ZECKENDORF ARITHMETIC" causes some odd behaviour, even though Fortran source normally involves spaces having no significance outside text literals.

      MODULE ZECKENDORF ARITHMETIC	!Using the Fibonacci series, rather than powers of some base.
       INTEGER ZLAST		!The standard 32-bit two's complement integers
       PARAMETER (ZLAST = 45)	!only get so far, just as there's a limit to the highest power.
       INTEGER F1B(ZLAST)	!I want the Fibonacci series, and, starting with its second one.
c       PARAMETER (F1B = (/1,2,	!But alas, the compiler doesn't allow
c     3  F1B(1) + F1B(2),		!for this sort of carpet-unrolling
c     4  F1B(2) + F1B(3), 		!initialisation sequence.
       INTEGER,PRIVATE:: F01,F02,F03,F04,F05,F06,F07,F08,F09,F10,	!So, not bothering with F00,
     1  F11,F12,F13,F14,F15,F16,F17,F18,F19,F20,	!Prepare a horde of simple names,
     2  F21,F22,F23,F24,F25,F26,F27,F28,F29,F30,	!which can be initialised
     3  F31,F32,F33,F34,F35,F36,F37,F38,F39,F40,	!in a certain way,
     4  F41,F42,F43,F44,F45				!without scaring the compiler.
       PARAMETER (F01 = 1, F02 = 2, F03 = F02 + F01, F04 = F03 + F02,	!Thusly.
     1  F05=F04+F03,F06=F05+F04,F07=F06+F05,F08=F07+F06,F09=F08+F07,	!Typing all this
     2  F10=F09+F08,F11=F10+F09,F12=F11+F10,F13=F12+F11,F14=F13+F12,	!is an invitation
     3  F15=F14+F13,F16=F15+F14,F17=F16+F15,F18=F17+F16,F19=F18+F17,	!for mistypes.
     4  F20=F19+F18,F21=F20+F19,F22=F21+F20,F23=F22+F21,F24=F23+F22,	!So a regular layout
     5  F25=F24+F23,F26=F25+F24,F27=F26+F25,F28=F27+F26,F29=F28+F27,	!helps a little.
     6  F30=F29+F28,F31=F30+F29,F32=F31+F30,F33=F32+F31,F34=F33+F32,	!Otherwise,
     7  F35=F34+F33,F36=F35+F34,F37=F36+F35,F38=F37+F36,F39=F38+F37,	!devise a prog.
     8  F40=F39+F38,F41=F40+F39,F42=F41+F40,F43=F42+F41,F44=F43+F42,	!to generate these texts...
     9  F45=F44+F43)	!The next is 2971215073. Too big for 32-bit two's complement integers.
       PARAMETER (F1B = (/F01,F02,F03,F04,F05,F06,F07,F08,F09,F10,	!And now,
     1  F11, F12, F13, F14, F15, F16, F17, F18, F19, F20,		!Here is the desired
     2  F21, F22, F23, F24, F25, F26, F27, F28, F29, F30,		!array of constants.
     3  F31, F32, F33, F34, F35, F36, F37, F38, F39, F40,		!And as such, possibly
     4  F41, F42, F43, F44, F45/))					!protected from alteration.
       CONTAINS	!After all that, here we go.
        SUBROUTINE ZECK(N,D)	!Convert N to a "Zeckendorf" digit sequence.
Counts upwards from digit one. D(i) ~ F1B(i). D(0) fingers the high-order digit.
         INTEGER N	!The normal number, in the computer's base.
         INTEGER D(0:)	!The digits, to be determined.
         INTEGER R	!The remnant.
         INTEGER L	!A finger, similar to the power of the base.
          IF (N.LT.0) STOP "ZECK! No negative numbers!"	!I'm not thinking about them.
          R = N		!Grab a copy that I can mess with.
          D = 0		!Scrub the lot in one go.
          L = ZLAST	!As if starting with BASE**MAX, rather than BASE**0.
   10     IF (R.GE.F1B(L)) THEN	!Has the remnant sufficient for this digit?
            R = R - F1B(L)		!Yes! Remove that amount.
            IF (D(0).EQ.0) THEN		!Is this the first non-zero digit?
              IF (L.GT.UBOUND(D,DIM=1)) STOP "ZECK! Not enough digits!"	!Yes.
              D(0) = L			!Remember the location of the high-order digit.
            END IF			!Two loops instead, to avoid repeated testing?
            D(L) = 1			!Place the digit, knowing a place awaits.
            L = L - 1			!Never need a ...11... sequence because F1B(i) + F1B(i+1) = F1B(i+2).
          END IF		!So much for that digit "power".
          L = L - 1		!Down a digit.
          IF (L.GT.0 .AND. R.GT.0) GO TO 10	!Are we there yet?
          IF (N.EQ.0) D(0) = 1	!Zero has one digit.
        END SUBROUTINE ZECK	!That was fun.

        INTEGER FUNCTION ZECKN(D)	!Converts a "Zeckendorf" digit sequence to a number.
         INTEGER D(0:)	!The digits. D(0) fingers the high-order digit.
          IF (D(0).LE.0) STOP "ZECKN! Empty number!"	!General paranoia.
          IF (D(0).GT.ZLAST) STOP "ZECKN! Oversize number!"	!I hate array bound hiccoughs.
          ZECKN = SUM(D(1:D(0))*F1B(1:D(0)))	!This is what positional notation means.
          IF (ZECKN.LT.0) STOP "ZECKN! Integer overflow!"	!Oh for IF OVERFLOW as in First Fortran.
        END FUNCTION ZECKN	!Overflows by a small amount will produce a negative number.
      END MODULE ZECKENDORF ARITHMETIC	!Odd stuff.

      PROGRAM POKE
      USE ZECKENDORF ARITHMETIC	!Please.
      INTEGER ZD(0:ZLAST)	!A scratchpad.
      INTEGER I,J,W
      CHARACTER*1 DIGIT(0:1)	!Assistance for the output.
      PARAMETER (DIGIT = (/"0","1"/), W = 6)	!This field width suffices.
c      WRITE (6,*) F1B
c      WRITE (6,*) INT8(F1B(44)) + INT8(F1B(45))
      WRITE (6,1) F1B(1:4),ZLAST,ZLAST,F1B(ZLAST),HUGE(I)	!Show some provenance.
    1 FORMAT ("Converts integers to their Zeckendorf digit string "
     1 "using the Fib1nacci sequence (",4(I0,","),
     2 " ...) as the equivalent of powers."/
     3 "At most, ",I0," digits because Fib1nacci(",I0,") = ",I0,
     4 " and the integer limit is ",I0,".",//,"  N     ZN")	!Ends with a heading.

      DO I = 0,20	!Step through the specified range.
        CALL ZECK(I,ZD)		!Convert I to ZD.
c       WRITE (6,2) I,ZD(ZD(0):1:-1)	!Show digits from high-order to low.
c   2   FORMAT (I3,1X,66I1)		!Or, WRITE (6,2) I,(ZD(J), J = ZD(0),1,-1)
        WRITE (6,3) I,(" ",J = ZD(0) + 1,W),DIGIT(ZD(ZD(0):1:-1))	!Right-aligned in field width W.
    3   FORMAT (I3,1X,66A1)		!The digits appear as characters.
        IF (I.NE.ZECKN(ZD)) STOP "Huh?"	!Should never happen...
      END DO		!On to the next.

      END

Output: shown aligned right for a more regular table. Producing leading spaces or digits required a conversion from a numerical digit to a character digit, so that all the output could use the A format code.

Converts integers to their Zeckendorf digit string using the Fib1nacci sequence (1,2,3,5, ...) as the equivalent of powers.
At most, 45 digits because Fib1nacci(45) = 1836311903 and the integer limit is 2147483647.

  N     ZN
  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

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
}

Output:

Haskell

Using "no consecutive 1s" rule:

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

which is the same as

zeckendorf = "0":"1":[s++[d] |	s <- tail zeckendorf, d <- "01",
				last s /= '1' || d /= '1']

main = mapM putStrLn $ take 21 zeckendorf

or a different way to generate the sequence:

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

Creating a string for an individual number:

import Data.List (mapAccumL)

fib :: [Int]
fib = 1 : 2 : zipWith (+) fib (tail fib)

zeckendorf :: Int -> String
zeckendorf 0 = "0"
zeckendorf n = snd $ mapAccumL f n $ reverse $ takeWhile (<= n) fib
  where
    f n x
      | n < x = (n, '0')
      | otherwise = (n - x, '1')

main :: IO ()
main = (putStrLn . unlines) $ zeckendorf <$> [0 .. 20]

Output:

J

Please enjoy our Zeckendorf essay.

fib=: 3 : 0 " 0
 mp=. +/ .*
 {.{: mp/ mp~^:(I.|.#:y) 2 2$0 1 1 1x
)

phi=: -:1+%:5

fi =: 3 : 'n - y<fib n=. 0>.(1=y)-~>.(phi^.%:5)+phi^.y'

fsum=: 3 : 0
 z=. 0$r=. y
 while. 3<r do.
  m=. fib fi r
  z=. z,m
  r=. r-m
 end.
 z,r$~(*r)+.0=y
)

Filter=: (#~`)(`:6)

' '&~:Filter@:":@:#:@:#.@:((|. fib 2+i.8) e. fsum)&.>i.3 7
┌──────┬──────┬──────┬──────┬──────┬──────┬──────┐
│0     │1     │10    │100   │101   │1000  │1001  │
├──────┼──────┼──────┼──────┼──────┼──────┼──────┤
│1010  │10000 │10001 │10010 │10100 │10101 │100000│
├──────┼──────┼──────┼──────┼──────┼──────┼──────┤
│100001│100010│100100│100101│101000│101001│101010│
└──────┴──────┴──────┴──────┴──────┴──────┴──────┘

Explanation:

fsum finds the canonical list of fibonacci terms which sum to its argument.

fib finds the nth fibonacci term of the fibonacci sequence. This would be 0 1 1 2 3 5 8 13 21 34 55 89 ... but we ignore the first two values of that sequence for the purpose of this exercise.

(|. fib 2+i.8) is 34 21 13 8 5 3 2 1. You can think of an eight bit Zeckendorf number such as 101010 as representing the inner product of its digits with (|. fib 2+i.8). Thus, we can find the relevant Zeckendorf bits by finding which which members of that sequence are in the result of fsum

The rest is just formatting. (We convert from binary list to integer and then back to binary list, to eliminate leading zeros from the list. Then we convert to text and remove all the spaces. Since we arranged for each result to be in a box, the boxes will align giving us a somewhat readable presentation.

Java

Code:

import java.util.*;

class Zeckendorf
{
  public static String getZeckendorf(int n)
  {
    if (n == 0)
      return "0";
    List<Integer> fibNumbers = new ArrayList<Integer>();
    fibNumbers.add(1);
    int nextFib = 2;
    while (nextFib <= n)
    {
      fibNumbers.add(nextFib);
      nextFib += fibNumbers.get(fibNumbers.size() - 2);
    }
    StringBuilder sb = new StringBuilder();
    for (int i = fibNumbers.size() - 1; i >= 0; i--)
    {
      int fibNumber = fibNumbers.get(i);
      sb.append((fibNumber <= n) ? "1" : "0");
      if (fibNumber <= n)
        n -= fibNumber;
    }
    return sb.toString();
  }
  
  public static void main(String[] args)
  {
    for (int i = 0; i <= 20; i++)
      System.out.println("Z(" + i + ")=" + getZeckendorf(i));
  }
}

Output:

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

Recursive Implementation

Code:

import java.util.ArrayList;
import java.util.List;

public class Zeckendorf {

    private List<Integer> getFibList(final int maxNum, final int n1, final int n2, final List<Integer> fibs){
        if(n2 > maxNum) return fibs;

        fibs.add(n2);

        return getFibList(maxNum, n2, n1 + n2, fibs);
    }

    public String getZeckendorf(final int num) {
        if (num <= 0) return "0";

        final List<Integer> fibs = getFibList(num, 1, 2, new ArrayList<Integer>(){{ add(1); }});

        return getZeckString("", num, fibs.size() - 1, fibs);
    }

    private String getZeckString(final String zeck, final int num, final int index, final List<Integer> fibs){
        final int curFib = fibs.get(index);
        final boolean placeZeck = num >= curFib;

        final String outString = placeZeck ? zeck + "1" : zeck + "0";
        final int outNum = placeZeck ? num - curFib : num;

        if(index == 0) return outString;

        return  getZeckString(outString, outNum, index - 1, fibs);
    }
    
    public static void main(final String[] args) {
        final Zeckendorf zeckendorf = new Zeckendorf();

        for(int i =0; i <= 20; i++){
            System.out.println("Z("+ i +"):\t" + zeckendorf.getZeckendorf(i));
        }
    }
}

Output:

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

JavaScript

ES6

Translation of: Haskell

(mapAccumuL example)

(() => {
    'use strict';

    const main = () =>
        unlines(
            map(n => concat(zeckendorf(n)),
                enumFromTo(0, 20)
            )
        );

    // zeckendorf :: Int -> String
    const zeckendorf = n => {
        const go = (n, x) =>
            n < x ? (
                Tuple(n, '0')
            ) : Tuple(n - x, '1')
        return 0 < n ? (
            snd(mapAccumL(
                go, n,
                reverse(fibUntil(n))
            ))
        ) : ['0'];
    };

    // fibUntil :: Int -> [Int]
    const fibUntil = n =>
        cons(1, takeWhile(x => n >= x,
            map(snd, iterateUntil(
                tpl => n <= fst(tpl),
                tpl => {
                    const x = snd(tpl);
                    return Tuple(x, x + fst(tpl));
                },
                Tuple(1, 2)
            ))));

    // GENERIC FUNCTIONS ----------------------------

    // Tuple (,) :: a -> b -> (a, b)
    const Tuple = (a, b) => ({
        type: 'Tuple',
        '0': a,
        '1': b,
        length: 2
    });

    // concat :: [[a]] -> [a]
    // concat :: [String] -> String
    const concat = xs =>
        0 < xs.length ? (() => {
            const unit = 'string' !== typeof xs[0] ? (
                []
            ) : '';
            return unit.concat.apply(unit, xs);
        })() : [];

    // cons :: a -> [a] -> [a]
    const cons = (x, xs) =>
        Array.isArray(xs) ? (
            [x].concat(xs)
        ) : (x + xs);

    // enumFromTo :: Int -> Int -> [Int]
    const enumFromTo = (m, n) =>
        m <= n ? iterateUntil(
            x => n <= x,
            x => 1 + x,
            m
        ) : [];

    // fst :: (a, b) -> a
    const fst = tpl => tpl[0];

    // iterateUntil :: (a -> Bool) -> (a -> a) -> a -> [a]
    const iterateUntil = (p, f, x) => {
        const vs = [x];
        let h = x;
        while (!p(h))(h = f(h), vs.push(h));
        return vs;
    };

    // map :: (a -> b) -> [a] -> [b]
    const map = (f, xs) => xs.map(f);

    // 'The mapAccumL function behaves like a combination of map and foldl;
    // it applies a function to each element of a list, passing an accumulating
    // parameter from left to right, and returning a final value of this
    // accumulator together with the new list.' (See Hoogle)

    // mapAccumL :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y])
    const mapAccumL = (f, acc, xs) =>
        xs.reduce((a, x, i) => {
            const pair = f(a[0], x, i);
            return Tuple(pair[0], a[1].concat(pair[1]));
        }, Tuple(acc, []));

    // reverse :: [a] -> [a]
    const reverse = xs =>
        'string' !== typeof xs ? (
            xs.slice(0).reverse()
        ) : xs.split('').reverse().join('');

    // snd :: (a, b) -> b
    const snd = tpl => tpl[1];

    // tail :: [a] -> [a]
    const tail = xs => 0 < xs.length ? xs.slice(1) : [];

    // takeWhile :: (a -> Bool) -> [a] -> [a]
    // takeWhile :: (Char -> Bool) -> String -> String
    const takeWhile = (p, xs) => {
        const lng = xs.length;
        return 0 < lng ? xs.slice(
            0,
            until(
                i => i === lng || !p(xs[i]),
                i => 1 + i,
                0
            )
        ) : [];
    };

    // unlines :: [String] -> String
    const unlines = xs => xs.join('\n');

    // until :: (a -> Bool) -> (a -> a) -> a -> a
    const until = (p, f, x) => {
        let v = x;
        while (!p(v)) v = f(v);
        return v;
    };

    // MAIN ---
    return main();
})();

Output:

jq

Works with: jq version 1.5

def zeckendorf:
  def fibs($n):
    # input: [f(i-2), f(i-1)]
    [1,1] | [recurse(select(.[1] < $n) | [.[1], add]) | .[1]] ;

  # Emit an array of 0s and 1s corresponding to the Zeckendorf encoding
  # $f should be the relevant Fibonacci numbers in increasing order.
  def loop($f):
    [ recurse(. as [$n, $ix]
              | select( $ix > -1 )
              | $f[$ix] as $next
              | if $n >= $next
	        then [$n - $next, $ix-1, 1]
                else [$n, $ix-1, 0]
                end )
      | .[2] // empty ]
    # remove any superfluous leading 0:
    # remove leading 0 if any unless length==1
    | if length>1 and .[0] == 0 then .[1:] else . end ;

  # state: [$n, index_in_fibs, digit ]
  fibs(.) as $f
  | [., ($f|length)-1]
  | loop($f)
  | join("") ;

Example:

range(0;21) | "\(.): \(zeckendorf)"

Output:

$ jq -n -r -f zeckendorf.jq
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

Julia

Translation of: Python

function zeck(n)
    n <= 0 && return 0
    fib = [2,1]; while fib[1] < n unshift!(fib,sum(fib[1:2])) end
    dig = Int[]; for f in fib f <= n ? (push!(dig,1); n = n-f;) : push!(dig,0) end
    return dig[1] == 0 ? dig[2:end] : dig
end

Output:

julia> for x = 0:20
           println(join(zeck(x)))
       end
0
1
10
100
101
1000
1001
1010
10000
10001
10010
10100
10101
100000
100001
100010
100100
100101
101000
101001
101010

Klingphix

include ..\Utilitys.tlhy

:listos
    %i$ "" !i$
    len [ get tostr $i$ chain !i$ ] for drop
    $i$
;


:Zeckendorf %n !n
    %i 0 !i %c 0 !c
 
    [
        $i 8 itob listos
        "11" find not (
            [ ( $c ":" 9 tochar ) lprint tonum ? $c 1 + !c ]
            [drop]          
        ) if
        $i 1 + !i
    ]
    [$c $n >] until
;

 
20 Zeckendorf

nl "End " input

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

End

Kotlin

// version 1.0.6

const val LIMIT = 46  // to stay within range of signed 32 bit integer
val fibs = fibonacci(LIMIT)

fun fibonacci(n: Int): IntArray {
    if (n !in 2..LIMIT) throw IllegalArgumentException("n must be between 2 and $LIMIT")
    val fibs = IntArray(n)
    fibs[0] = 1
    fibs[1] = 1
    for (i in 2 until n) fibs[i] = fibs[i - 1] + fibs[i - 2]
    return fibs
}

fun zeckendorf(n: Int): String {
    if (n < 0) throw IllegalArgumentException("n must be non-negative")
    if (n < 2) return n.toString()
    var lastFibIndex = 1
    for (i in 2..LIMIT)
        if (fibs[i] > n) {
            lastFibIndex = i - 1
            break
        }
    var nn = n - fibs[lastFibIndex--]
    val zr = StringBuilder("1")
    for (i in lastFibIndex downTo 1)
        if (fibs[i] <= nn) {
            zr.append('1')
            nn -= fibs[i]
        } else {
            zr.append('0')
        }
    return zr.toString()
}

fun main(args: Array<String>) {
    println(" n   z")
    for (i in 0..20) println("${"%2d".format(i)} : ${zeckendorf(i)}")
}

Output:

 n   z
 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

Lingo

Translation of: Lua

-- Return the distinct Fibonacci numbers not greater than 'n'
on fibsUpTo (n)
    fibList = []
    last = 1
    current = 1
    repeat while current <= n
        fibList.add(current)
        nxt = last + current
        last = current
        current = nxt    
    end repeat
    return fibList
end
 
-- Return the Zeckendorf representation of 'n'
on zeckendorf (n)
    fib = fibsUpTo(n)
    zeck = ""
    repeat with pos = fib.count down to 1
        if n >= fib[pos] then
            zeck = zeck & "1"
            n = n - fib[pos]
        else
            zeck = zeck & "0"
        end if
    end repeat
    if zeck = "" then return "0"
    return zeck
end

repeat with n = 0 to 20
    put n & ": " & zeckendorf(n)
end repeat

Output:

Little Man Computer

Runs in Peter Higginson's LMC simulator. Uses his non-standard OTC instruction to output the character whose ASCII code is in the accumulator.

Most online LMC simulators seem to have very limited space for output. Peter Higginson's allows only sixteen lines of four characters each. Previous output scrolls off and is lost. The output from this program had to be captured by repeatedly pausing the program and using copy-and-paste.

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

Output:

[formatted manually]
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

Logo

; return the (N+1)th Fibonacci number (1,2,3,5,8,13,...)
to fib m
  local "n
  make "n sum :m 1
  if [lessequal? :n 0] [output difference fib sum :n 2 fib sum :n 1]
  global "_fib
  if [not name? "_fib] [
    make "_fib [1 1]
  ]
  local "length
  make "length count :_fib
  while [greater? :n :length] [
    make "_fib (lput (sum (last :_fib) (last (butlast :_fib))) :_fib)
    make "length sum :length 1
  ]
  output item :n :_fib
end

; return the binary Zeckendorf representation of a nonnegative number
to zeckendorf n
  if [less? :n 0] [(throw "error [Number must be nonnegative.])]
  (local "i "f "result)
  make "i :n
  make "f fib :i
  while [less? :f :n] [make "i sum :i 1 make "f fib :i]

  make "result "||
  while [greater? :i 0] [
    ifelse [greaterequal? :n :f] [
      make "result lput 1 :result
      make "n difference :n :f
    ] [
      if [not empty? :result] [
        make "result lput 0 :result
      ]
    ]
    make "i difference :i 1
    make "f fib :i
  ]
  if [equal? :result "||] [
    make "result 0
  ]
  output :result
end

type zeckendorf 0
repeat 20 [
  type word "| | zeckendorf repcount
]
print []
bye

Output:

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

Lua

-- Return the distinct Fibonacci numbers not greater than 'n'
function fibsUpTo (n)
    local fibList, last, current, nxt = {}, 1, 1
    while current <= n do
        table.insert(fibList, current)
        nxt = last + current
        last = current
        current = nxt    
    end
    return fibList
end

-- Return the Zeckendorf representation of 'n'
function zeckendorf (n)
    local fib, zeck = fibsUpTo(n), ""
    for pos = #fib, 1, -1 do
        if n >= fib[pos] then
            zeck = zeck .. "1"
            n = n - fib[pos]
        else
            zeck = zeck .. "0"
        end
    end
    if zeck == "" then return "0" end
    return zeck
end

-- Main procedure
print(" n\t| Zeckendorf(n)")
print(string.rep("-", 23))
for n = 0, 20 do
    print(" " .. n, "| " .. zeckendorf(n))
end

Output:

 n      | Zeckendorf(n)
-----------------------
 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

Mathematica /Wolfram Language

ZeckendorfRepresentation[0] = 0;

ZeckendorfRepresentation[n_Integer?Positive]:= 
 NumberDecompose[n, Reverse@Fibonacci@Range[2,1000]] // FromDigits

ZeckendorfRepresentation /@ Range[0, 20]

Output:

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

MATLAB

Translation of: Julia

clear all; close all; clc;

% Print the sequence for numbers from 0 to 20
for x = 0:20
    zeckString = arrayfun(@num2str, zeck(x), 'UniformOutput', false);
    zeckString = strjoin(zeckString, '');
    fprintf("%d : %s\n", x, zeckString);
end

function dig = zeck(n)
    if n <= 0
        dig = 0;
        return;
    end
    
    fib = [1, 2];
    while fib(end) < n
        fib(end + 1) = sum(fib(end-1:end));
    end
    fib = fliplr(fib); % Reverse the order of Fibonacci numbers
    
    dig = [];
    for i = 1:length(fib)
        if fib(i) <= n
            dig(end + 1) = 1;
            n = n - fib(i);
        else
            dig(end + 1) = 0;
        end
    end
    
    if dig(1) == 0
        dig = dig(2:end);
    end
end

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

MiniScript

fibonacci = function(val)
	if val < 1 then return []
	fib = []
	a = 1; b = 2
	while  a <= val
		fib.insert(0, a)
		next = a + b
		a = b
		b = next
	end while
	return fib
end function

zeckendorf = function(val)
	seq = fibonacci(val)
	s = ""
	for i in seq
		onOff = val >= i and (s == "" or s[-1] == "0")
		s += str(onOff)
		val -= (i*onOff)
	end for
	return s
end function

for i in range(1, 20)
	print [i, zeckendorf(i)]
end for

Output:

[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"]

Nim

Translation of: Python

import strformat, strutils
 
proc z(n: Natural): string =
  if n == 0: return "0"
  var fib = @[2,1]
  var n = n
  while fib[0] < n: fib.insert(fib[0] + fib[1])
  for f in fib:
    if f <= n:
      result.add '1'
      dec n, f
    else:
      result.add '0'
  if result[0] == '0':
    result = result[1..result.high]
 
for i in 0 .. 20:
  echo &"{i:>3} {z(i):>8}"

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

OCaml

let zeck n =
  let rec enc x s = function
    | h :: t when h <= x -> enc (x - h) (s ^ "1") t
    | _ :: t -> enc x (s ^ "0") t
    | _ -> s
  and fib b a l =
    if b > n
    then enc (n - a) "1" l
    else fib (b + a) b (a :: l)
  in
  if n = 0 then "0" else fib 2 1 []

let () =
  for i = 0 to 20 do Printf.printf "%3u:%8s\n" i (zeck i) done

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

PARI/GP

Z(n)=if(!n,print1(0));my(k=2);while(fibonacci(k)<=n,k++); forstep(i=k-1,2,-1,print1(if(fibonacci(i)<=n,n-=fibonacci(i);1,0)));print
for(n=0,20,Z(n))

Pascal

A console application in Free Pascal, created with the Lazarus IDE. Though written independently of the Tcl solution, it uses essentially the same algorithm.

program ZeckendorfRep_RC;

{$mode objfpc}{$H+}

uses SysUtils;

// Return Zeckendorf representation of the passed-in cardinal.
function ZeckRep( C : cardinal) : string;
var
  a, b, rem : cardinal;
  j, nrDigits: integer;
begin
  // Case C = 0 has to be treated specially
  if (C = 0) then begin
    result := '0';
    exit;
  end;
  // Find largest Fibonacci number not exceeding C
  a := 1;
  b := 1;
  nrDigits := 1;
  rem := C - 1;
  while (rem >= b) do begin
    dec( rem, b);
    inc( a, b);
    b := a - b;
    inc( nrDigits);
  end;
  // Fill in digits by reversing Fibonacci back to start
  SetLength( result, nrDigits);
  j := 1;
  result[j] := '1';
  for j := 2 to nrDigits do begin
    if (rem >= b) then begin
      dec( rem, b);
      result[j] := '1';
    end
    else result[j] := '0';
    b := a - b;
    dec( a, b);
  end;
//  Assert((a = 1) and (b = 1)); // optional check
end;

// Main routine
var
  C : cardinal;
begin
  for C := 1 to 20 do
    WriteLn( SysUtils.Format( '%2d: %s', [C, ZeckRep(C)]));
end.

Output:

Perl

my @fib;

sub fib {
  my $n = shift;
  return 1 if $n < 2;
  return $fib[$n] //= fib($n-1)+fib($n-2);
}

sub zeckendorf {
  my $n = shift;
  return "0" unless $n;
  my $i = 1;
  $i++ while fib($i) <= $n;
  my $z = '';
  while( --$i ) {
    $z .= "0", next if fib( $i ) > $n;
    $z .= "1";
    $n -= fib( $i );
  }
  return $z;
}

printf "%4d: %8s\n", $_, zeckendorf($_) for 0..20;

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

Phix

function zeckendorf(integer n)
integer r = 0, c
sequence fib = {1,1}
    while fib[$]<n do
        fib &= fib[$] + fib[$-1]
    end while
    for i=length(fib) to 2 by -1 do
        c = n>=fib[i]
        r += r+c
        n -= c*fib[i]
    end for
    return r
end function
 
for i=0 to 20 do
    printf(1,"%2d: %7b\n",{i,zeckendorf(i)})
end for

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

Phixmonti

def Zeckendorf  /# n -- #/
    0 var i 0 var c 1 1 2 tolist var pattern
    true
    while
        i 8 int>bit reverse
        pattern find
        not if
            c print ":\t" print print nl
            dup c == if
                false
            else
                c 1 + var c
                true
            endif
        endif
        i 1 + var i
    endwhile
    drop
enddef

20 Zeckendorf

PHP

<?php
$m = 20;
 
$F = array(1,1);
while ($F[count($F)-1] <= $m)
   $F[] = $F[count($F)-1] + $F[count($F)-2];
 
while ($n = $m--) {
   while ($F[count($F)-1] > $n) array_pop($F);
   $l = count($F)-1;
   print "$n: ";
   while ($n) {
      if ($n >= $F[$l]) {
         $n = $n - $F[$l];
         print '1';
      } else print '0';
      --$l;
   }
   print str_repeat('0',$l);
   print "\n";
}
?>

Output:

Picat

Constraint model

go =>
  foreach(Num in 0..20)
    zeckendorf_cp(Num,X,F),
    Nums = [F[I] : I in 1..X.length, X[I] = 1],
    printf("%2d %6s %w\n",Num, rep(X),Nums),
  end,
  nl.

zeckendorf_cp(Num, X,F) =>
  F = get_fibs(Num).reverse(),
  N = F.length,
  X = new_list(N),
  X :: 0..1,

  % From the task description:
  % """
  % 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.
  % """
  foreach(I in 2..N)
    X[I-1] #= 1 #=> X[I] #= 0
  end,

  scalar_product(F,X,Num),
 
  solve([ff,split],X).

%
% Fibonacci numbers
%
table
fib(0) = 0.
fib(1) = 1.
fib(N) = fib(N-1) + fib(N-2).

%
% Remove leading 0's and stringify it
%
rep(X) = Str =>
  First = 1,
  if X.length > 1, X[First] = 0 then
    while (X[First] == 0) 
      First := First + 1
    end
  end,
  Str = [X[I].to_string() : I in First..X.length].join('').

%
% Return a list of fibs <= N
%
get_fibs(N) = Fibs =>
  I = 2,
  Fib = fib(I),
  Fibs1 = [Fib],
  while (Fib < N)
    I := I + 1,
    Fib := fib(I),
    Fibs1 := Fibs1 ++ [Fib]
  end,
  Fibs = Fibs1.

Output:

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

An iterative approach

go2 =>
  foreach(Num in 0..20)
    zeckendorf2(Num,X,F),
    Nums = [F[I] : I in 1..X.length, X[I]= 1],
    printf("%2d %6s %w\n",Num, rep(X),Nums)    
  end,
  nl.

zeckendorf2(0, [0],[0]).
zeckendorf2(Num, X,F) :-
  Fibs = get_fibs(Num),
  I = Fibs.length,
  N = Num,
  X1 = [],
  while (I > 0)
     Fib := Fibs[I],
     X1 := X1 ++ [cond(Fib > N,0,1)],
     if Fib <= N then 
       N := N - Fib
     end,
     I := I - 1
  end,
  X = X1,
  F = Fibs.reverse().

PicoLisp

(de fib (N)
   (let Fibs (1 1)
      (while (>= N (+ (car Fibs) (cadr Fibs)))
         (push 'Fibs (+ (car Fibs) (cadr Fibs))) )
      (uniq Fibs) ) )

(de zecken1 (N)
   (make
      (for I (fib N)
         (if (> I N)
            (link 0)
            (link 1)
            (dec 'N I) ) ) ) )

(de zecken2 (N)
   (make
      (when (=0 N) (link 0))
      (for I (fib N)
         (when (<= I N)
            (link I)
            (dec 'N I) ) ) ) )

(for (N 0 (> 21 N) (inc N))
   (tab (2 4 6 2 -10)
      N 
      " -> "
      (zecken1 N)
      "  "
      (glue " + " (zecken2 N)) ) ) 

(bye)

Output:

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

Plain $T e X$

This code needs an etex engine.

\def\genfibolist#1{% #creates the fibo list which sum>=#1
	\let\fibolist\empty\def\targetsum{#1}\def\fibosum{0}%
	\genfibolistaux1,1\relax
}
\def\genfibolistaux#1,#2\relax{%
	\ifnum\fibosum<\targetsum\relax
		\edef\fibosum{\number\numexpr\fibosum+#2}%
		\edef\fibolist{#2,\fibolist}%
		\edef\tempfibo{\noexpand\genfibolistaux#2,\number\numexpr#1+#2\relax\relax}%
		\expandafter\tempfibo
	\fi
}
\def\zeckendorf#1{\expandafter\zeckendorfaux\fibolist,\relax#1\relax\relax0}
\def\zeckendorfaux#1,#2\relax#3\relax#4\relax#5{%
	\ifx\relax#2\relax
		#4%
	\else
		\ifnum#3<#1
			\edef\temp{#2\relax#3\relax#4\ifnum#5=1 0\fi\relax#5}%
		\else
			\edef\temp{#2\relax\number\numexpr#3-#1\relax\relax#41\relax1}%
		\fi
		\expandafter\expandafter\expandafter\zeckendorfaux\expandafter\temp
	\fi
}
\newcount\ii
\def\listzeckendorf#1{%
	\genfibolist{#1}%
	\ii=0
	\loop
		\ifnum\ii<#1
		\advance\ii1
		\number\ii: \zeckendorf\ii\endgraf
	\repeat
}
\listzeckendorf{20}% any integer accepted
\bye

pdf output looks like:

PowerShell

Works with: PowerShell version 2

function Get-ZeckendorfNumber ( $N )
    {
    #  Calculate relevant portation of Fibonacci series
    $Fib = @( 1, 1 )
    While ( $Fib[-1] -lt $N ) { $Fib += $Fib[-1] + $Fib[-2] }
 
    #  Start with 0
    $ZeckendorfNumber = 0
 
    #  For each number in the relevant portion of Fibonacci series
    For ( $i = $Fib.Count - 1; $i -gt 0; $i-- )
        {
        #  If Fibonacci number is less than or equal to remainder of N
        If ( $Fib[$i] -le $N )
            {
            #  Double Z number and add 1 (equivalent to adding a '1' to the end of a binary number)
            $ZeckendorfNumber = $ZeckendorfNumber * 2 + 1
            #  Reduce N by Fibonacci number, skip next Fibonacci number
            $N -= $Fib[$i--]
            }
        #  If were aren't finished yet, double Z number
        #  (equivalent to adding a '0' to the end of a binary number)
        If ( $i ) { $ZeckendorfNumber *= 2 }
        }
    return $ZeckendorfNumber
    }

#  Get Zeckendorf numbers through 20, convert to binary for display
0..20 | ForEach { [convert]::ToString( ( Get-ZeckendorfNumber $_ ), 2 ) }

Output:

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))))

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

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))))

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

Quackery

Converting non-negative integers to and from Zeckendorf representation.

  [ 2 base put
    echo
    base release ]        is binecho ( n -->   )

  [ 0 swap ' [ 2 1 ]
    [ 2dup 0 peek < iff
        [ behead drop ]
        done
      dup 0 peek
      over 1 peek
      + swap join again ]
    witheach
      [ rot 1 << unrot
        2dup < iff drop
        else
          [ -
            dip
              [ 1 | ] ] ]
    drop ]                is n->z    ( n --> z )

  [ 0 temp put
    1 1 rot
    [ dup while
      dup 1 & if
        [ over
          temp tally ]
      1 >>
      dip [ tuck + ]
      again ]
    2drop drop
    temp take ]           is z->n    ( z --> n )

   21 times
     [ i^ dup echo
       say " -> "
       n->z dup binecho
       say " -> "
       z->n echo cr ]

Output:

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

R

zeckendorf <- function(number) {

  # Get an upper limit on Fibonacci numbers needed to cover number
  indexOfFibonacciNumber <- function(n) {
    if (n < 1) {
      2
    } else {
      Phi <- (1 + sqrt(5)) / 2
      invertClosedFormula <- log(n * sqrt(5)) / log(Phi)
      ceiling(invertClosedFormula)
    }
  }

  upperLimit <- indexOfFibonacciNumber(number)

  # Return the sequence as digits, sorted descending
  fibonacciSequenceDigits <- function(n) {
    fibGenerator <- function(f, ...) { c(f[2], sum(f)) }
    fibSeq <- Reduce(fibGenerator, 1:n, c(0,1), accumulate=TRUE)

    fibNums <- unlist(lapply(fibSeq, head, n=1))

    # drop last F0 and F1 and reverse sequence
    rev(fibNums[-2:-1])
  }

  digits <- fibonacciSequenceDigits(upperLimit)

  isInNumber <- function(digit) {
    if (number >= digit) {
      number <<- number - digit
      1
    } else {
      0
    }
  }

  zeckSeq <- Map(isInNumber, digits)

  # drop leading 0 and convert to String
  gsub("^0+1", "1", paste(zeckSeq, collapse=""))
}

print(unlist(lapply(0:20, zeckendorf)))

This is definitely not the shortest way to implement the Zeckendorf numbers but focus was on the functional aspect of R, so no loops and (almost) no assignments.

Output:

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

Racket

#lang racket (require math)

(define (fibs n)
  (reverse
   (for/list ([i (in-naturals 2)] #:break (> (fibonacci i) n))
     (fibonacci i))))

(define (zechendorf n)
  (match/values
   (for/fold ([n n] [xs '()]) ([f (fibs n)])
     (if (> f n)
         (values n       (cons 0 xs))
         (values (- n f) (cons 1 xs))))
   [(_ xs) (reverse xs)]))

(for/list ([n 21])
  (list n (zechendorf n)))

Output:

'((0 ())
  (1 (1))
  (2 (1 0))
  (3 (1 0 0))
  (4 (1 0 1))
  (5 (1 0 0 0))
  (6 (1 0 0 1))
  (7 (1 0 1 0))
  (8 (1 0 0 0 0))
  (9 (1 0 0 0 1))
  (10 (1 0 0 1 0))
  (11 (1 0 1 0 0))
  (12 (1 0 1 0 1))
  (13 (1 0 0 0 0 0))
  (14 (1 0 0 0 0 1))
  (15 (1 0 0 0 1 0))
  (16 (1 0 0 1 0 0))
  (17 (1 0 0 1 0 1))
  (18 (1 0 1 0 0 0))
  (19 (1 0 1 0 0 1))
  (20 (1 0 1 0 1 0)))

Raku

(formerly Perl 6)

Works with: rakudo version 2015.12

printf "%2d: %8s\n", $_, zeckendorf($_) for 0 .. 20;

multi zeckendorf(0) { '0' }
multi zeckendorf($n is copy) {
    constant FIBS = (1,2, *+* ... *).cache;
    [~] map {
        $n -= $_ if my $digit = $n >= $_;
        +$digit;
    }, reverse FIBS ...^ * > $n;
}

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

specific to 20

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

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

generalized

This generalized REXX version will work for any Zeckendorf number (up to 100,000 decimal digits).

A list of Fibonacci numbers (in ascending order) is generated large enough to handle the N^th Zeckendorf number.

/*REXX program  calculates and displays the  first   N   Zeckendorf numbers.            */
numeric digits 100000                            /*just in case user gets real ka─razy. */
parse arg N .                                    /*let the user specify the upper limit.*/
if N=='' | N==","  then n=20;   w= length(N)     /*Not specified?  Then use the default.*/
@.1= 1                                           /*start the array with  1   and   2.   */
@.2= 2;   do  #=3  until #>=N;  p= #-1;  pp= #-2 /*build a list of Fibonacci numbers.   */
          @.#= @.p + @.pp                        /*sum the last two Fibonacci numbers.  */
          end   /*#*/                            /* [↑]   #:  contains a Fibonacci list.*/

  do j=0  to N;             parse var j x z      /*task:  process zero  ──►  N  numbers.*/
     do k=#  by -1  for #;  _= @.k               /*process all the Fibonacci numbers.   */
     if x>=_  then do;      z= z'1'              /*is X>the next Fibonacci #?  Append 1.*/
                            x= x - _             /*subtract this Fibonacci # from index.*/
                   end
              else z= z'0'                       /*append zero (0)  to the Fibonacci #. */
     end   /*k*/
  say '    Zeckendorf'     right(j, w)    "="     right(z+0, 30)     /*display a number.*/
  end     /*j*/                                  /*stick a fork in it,  we're all done. */

output when using the default input:

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

generic

This generic REXX version will generate up to the N^th Zeckendorf numbers (up to 100,000 decimal digits) by
using binary numbers that don't have two consecutive 11s within their binary version.

There isn't any need to generate a Fibonacci series with this method. This method is extremely fast.

/*REXX program  calculates and displays the  first   N   Zeckendorf numbers.            */
numeric digits 100000                            /*just in case user gets real ka─razy. */
parse arg N .                                    /*let the user specify the upper limit.*/
if N=='' | N==","  then n=20;    w= length(N)    /*Not specified?  Then use the default.*/
z=0                                              /*the index of a  Zeckendorf number.   */
    do j=0  until z>N;          _=x2b( d2x(j) )  /*task:   process zero  ──►   N.       */
    if pos(11, _) \== 0  then iterate            /*are there two consecutive ones (1s) ?*/
    say '    Zeckendorf'   right(z, w)    "="     right(_+0, 30)     /*display a number.*/
    z= z + 1                                     /*bump the  Zeckendorf  number counter.*/
    end   /*j*/                                  /*stick a fork in it,  we're all done. */

output is identical to the previous (generalized) version.

Ring

# Project : Zeckendorf number representation

see "0 0" + nl
for n = 1 to 20
     see "" + n + " " + zeckendorf(n) + nl
next
 
func zeckendorf(n)
       fib = list(45)
       fib[1] = 1
       fib[2] = 1
       i = 2
       o = ""
       while fib[i] <= n
               i = i + 1
               fib[i] = fib[i-1] + fib[i-2]
       end
       while i != 2
               i = i - 1
               if n >= fib[i]
                   o = o + "1"
                   n = n - fib[i]
               else
                   o = o + "0"
               ok
        end
        return o

Output:

RPL

The two-step algorithm - first generating a series a Fibonacci numbers, then encrypting - is an opportunity to showcase the structured programming that RPL allows, with two separate structures having each their own local variables to avoid too complex stack handlings.

Works with: Halcyon Calc version 4.2.7

≪ → m 
  ≪ { 1 } 1 1 
     DO 
       ROT OVER SWAP + 
       ROT ROT SWAP OVER + 
     UNTIL DUP m > END
     DROP2 m SWAP 
  ≫ 
  → fibs 
  ≪ "" SWAP 
     1 fibs SIZE 1 - FOR j
        fibs j GET 
       IF DUP2 ≥ THEN - SWAP "1" ELSE DROP SWAP "0" END
        + SWAP 
     NEXT 
     DROP 
  ≫ 
≫
'→ZKDF' STO

≪ { } 1 20 FOR j j →ZKDF + NEXT ≫ EVAL

Output:

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

Ruby

Featuring a method doubling as an enumerator.

def zeckendorf
  return to_enum(__method__) unless block_given?
  x = 0
  loop do
    bin = x.to_s(2)
    yield bin unless bin.include?("11") 
    x += 1
  end
end

zeckendorf.take(21).each_with_index{|x,i| puts "%3d: %8s"% [i, x]}

Translation of: Python

def zeckendorf(n)
  return 0 if n.zero?
  fib = [1,2]
  fib << fib[-2] + fib[-1] while fib[-1] < n
  dig = ""
  fib.reverse_each do |f|
    if f <= n
      dig, n = dig + "1", n - f
    else
      dig += "0"
    end
  end
  dig.to_i
end

for i in 0..20
  puts '%3d: %8d' % [i, zeckendorf(i)]
end

As oneliner.

Translation of: Crystal

def zeckendorf(n)
  0.step.lazy.map { |x| x.to_s(2) }.reject { |z| z.include?("11") }.first(n)
end

zeckendorf(21).each_with_index{ |x,i| puts "%3d: %8s"% [i, x] }

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

Rust

Translation of: C#

use std::collections::VecDeque;

fn fibonacci(n: u32) -> u32 {
    match n {
        0 => 0,
        1 => 1,
        _ => fibonacci(n - 1) + fibonacci(n - 2),
    }
}

fn zeckendorf(num: u32) -> String {
    let mut fibonacci_numbers = VecDeque::new();
    let mut fib_position = 2;
    let mut current_fibonacci_num = fibonacci(fib_position);

    while current_fibonacci_num <= num {
        fibonacci_numbers.push_front(current_fibonacci_num);
        fib_position += 1;
        current_fibonacci_num = fibonacci(fib_position);
    }

    let mut temp = num;
    let mut output = String::new();

    for item in fibonacci_numbers {
        if item <= temp {
            output.push('1');
            temp -= item;
        } else {
            output.push('0');
        }
    }

    output
}

fn main() {
    for i in 1..=20 {
        let zeckendorf_representation = zeckendorf(i);
        println!("{} : {}", i, zeckendorf_representation);
    }
}

Output:

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

Scala

def zNum( n:BigInt ) : String = {

  if( n == 0 ) return "0"	// Short-circuit this and return zero if we were given zero


  val v = n.abs

  val fibs : Stream[BigInt] = { def series(i:BigInt,j:BigInt):Stream[BigInt] = i #:: series(j, i+j); series(1,0).tail.tail.tail }


  def z( v:BigInt ) : List[BigInt] = if(v == 0) List() else {val m = fibs(fibs.indexWhere(_>v) - 1); m :: z(v-m)}

  val zv = z(v)
  
  // Walk the list of fibonacci numbers from the number that matches the most significant down to 1,
  // if the zeckendorf matchs then yield '1' otherwise '0'
  val s = (for( i <- (fibs.indexWhere(_==zv(0)) to 0 by -1) ) yield {
  
    if( zv.contains(fibs(i))) "1" else "0"
	
  }).mkString
  
  if( n < 0 ) "-" + s		// Using a negative-sign instead of twos-complement 
  else s
}


// A little test...
(0 to 20) foreach( i => print( zNum(i) + "\n" ) )

Output:

Scheme

Translation of: Java

(import (rnrs))

(define (getFibList maxNum n1 n2 fibs)
  (if (> n2 maxNum)
      fibs
      (getFibList maxNum n2 (+ n1 n2) (cons n2 fibs))))

(define (getZeckendorf num)
  (if (<= num 0)
      "0"
      (let ((fibs (getFibList num 1 2 (list 1))))
        (getZeckString "" num fibs))))

(define (getZeckString zeck num fibs)
  (let* ((curFib (car fibs))
         (placeZeck (>= num curFib))
         (outString (string-append zeck (if placeZeck "1" "0")))
         (outNum (if placeZeck (- num curFib) num)))
    (if (null? (cdr fibs))
        outString
        (getZeckString outString outNum (cdr fibs)))))

(let loop ((i 0))
  (when (<= i 20)
    (for-each
      (lambda (item)
        (display item))
      (list "Z(" i "):\t" (getZeckendorf i)))
    (newline)
    (loop (+ i 1))))

Output:

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

Sidef

Translation of: Perl

func fib(n) is cached {
    n < 2 ? 1
          : (fib(n-1) + fib(n-2))
}

func zeckendorf(n) {
    n == 0 && return '0'
    var i = 1
    ++i while (fib(i) <= n)
    gather {
        while (--i > 0) {
            var f = fib(i)
            f > n ? (take '0')
                  : (take '1'; n -= f)
        }
    }.join
}

for n (0..20) {
    printf("%4d: %8s\n", n, zeckendorf(n))
}

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

Simula

Translation of: Sinclair ZX81 BASIC

BEGIN
   INTEGER N, F0, F1, F2, D;
   N := 20;
   COMMENT CALCULATE D FROM ANY GIVEN N ;
   F1 := 1; F2 := 2; F0 := F1 + F2; D := 2;
   WHILE F0 < N DO BEGIN
      F1 := F2; F2 := F0; F0 := F1 + F2; D := D + 1;
   END;
   BEGIN
      COMMENT Sinclair ZX81 BASIC Solution ;
      TEXT Z1, S1;
      INTEGER I, J, Z;
      INTEGER ARRAY F(1:D);                  !  10 dim f(6) ;
      F(1) := 1;                             !  20 let f(1)=1 ;
      F(2) := 2;                             !  30 let f(2)=2 ;
      FOR I := 3 STEP 1 UNTIL D DO BEGIN     !  40 for i=3 to 6 ;
         F(I) := F(I-2) + F(I-1);            !  50 let f(i)=f(i-2)+f(i-1) ;
      END;                                   !  60 next i ;
      FOR I := 0 STEP 1 UNTIL N DO BEGIN     !  70 for i=0 to 20 ;
         Z1 :- "";                           !  80 let z$="" ;
         S1 :- " ";                          !  90 let s$=" " ;
         Z := I;                             ! 100 let z=i ;
         FOR J := D STEP -1 UNTIL 1 DO BEGIN ! 110 for j=6 to 1 step -1 ;
            IF J=1 THEN S1 :- "0";           ! 120 if j=1 then let s$="0" ;
            IF NOT (Z<F(J)) THEN BEGIN       ! 130 if z<f(j) then goto 180 ;
               Z1 :- Z1 & "1";               ! 140 let z$=z$+"1" ;
               Z := Z-F(J);                  ! 150 let z=z-f(j) ;
               S1 :- "0";                    ! 160 let s$="0" ;
            END ELSE                         ! 170 goto 190 ;
               Z1 :- Z1 & S1;                ! 180 let z$=z$+s$ ;
         END;                                ! 190 next j ;
         OUTINT(I, 0); OUTCHAR(' ');         ! 200 print i ; !" "; !;
         IF I<10 THEN OUTCHAR(' ');          ! 210 if i<10 then print " "; !;
         OUTTEXT(Z1); OUTIMAGE;              ! 220 print z$ ;
      END;                                   ! 230 next i ;
   END;
END

Output:

Standard ML

val zeckList = fn from => fn to =>

 let
  open IntInf

 val rec npow = fn n => fn 0 => fromInt 1 | m => n* (npow n (m-1)) ;

 val fib = fn 0 => 1 | 1 => 1 | n => let   val rec fb = fn x => fn y => fn 1=>y | n=> fb y (x+y) (n-1)  in
        fb 0 1  n
     end;

 val argminfi =  fn n =>                                          (* lowest k with fibonacci number over n *)
   let
      val rec afb = fn k => if fib k > n then k else afb (k+1)
   in
      afb 0
   end;

 val Zeck = fn n =>
   let
      val rec calzk = fn (0,z) => (0,z)
                       | (n,z) => let  val k =  argminfi n  in
                                     calzk ( n - fib (k-1) , z + (npow 10 (k-3) ) )
				  end
   in
      #2 (calzk (n,0))
  end

 in
     List.tabulate (toInt ( to - from) ,
                    fn i:Int.int => ( from + (fromInt i),
	            Zeck ( from + (fromInt i) ))) 
end;

output

List.app ( fn e => print ( (IntInf.toString (#1 e)) ^"  :  "^ (IntInf.toString (#2 e)) ^ "\n" )) (zeckList 1 21) ;
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

zeckList 0x21e320a3 0x21e320a4 ;
val it = [(568533155, 100100100101001001001000000100100010100101)]:
 : (IntInf.int * IntInf.int) list

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

# 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 ""]
}

Demonstration

for {set i 0} {$i <= 20} {incr i} {
    puts [format "%2d:%9s" $i [zeckendorf $i]]
}

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

UNIX Shell

set -- 2 1
x=-1
while [ $((x += 1)) -le 20 ]
do
        [ $x -gt $1 ] && set -- $(($2 + $1)) "$@"
        n=$x zeck=''
        for fib
        do
                zeck=$zeck$((n >= fib && (n -= fib) + 1))
        done
        echo "$x: ${zeck#0}"
done

Output:

V (Vlang)

Translation of: Go

fn main() {
    for i := 0; i <= 20; i++ {
        println("${i:2} ${zeckendorf(i):7b}")
    }
}
 
fn 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
}
 
fn zr(fib0 int, fib1 int, n int, bit u32) (int, int) {
    mut set := 0
    mut remaining := 0
    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 remaining, set
}

Output:

Wren

Translation of: Kotlin

Library: Wren-fmt

import "./fmt" for Fmt

var LIMIT = 46  // to stay within range of signed 32 bit integer

var fibonacci = Fn.new { |n|
    if (n < 2 || n > LIMIT) Fiber.abort("n must be between 2 and %(LIMIT)")
    var fibs = List.filled(n, 1)
    for (i in 2...n) fibs[i] = fibs[i - 1] + fibs[i - 2]
    return fibs
}

var fibs = fibonacci.call(LIMIT)

var zeckendorf = Fn.new { |n|
    if (n < 0) Fiber.abort("n must be non-negative")
    if (n < 2) return n.toString
    var lastFibIndex = 1
    for (i in 2..LIMIT) {
        if (fibs[i] > n) {
            lastFibIndex = i - 1
            break
        }
    }
    n = n - fibs[lastFibIndex]
    lastFibIndex = lastFibIndex - 1
    var zr = "1"
    for (i in lastFibIndex..1) {
        if (fibs[i] <= n) {
            zr = zr + "1"
            n = n - fibs[i]
        } else {
            zr = zr + "0"
        }
    }
    return zr
}

System.print(" n   z")
for (i in 0..20) Fmt.print("$2d : $s", i, zeckendorf.call(i))

Output:

 n   z
 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

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 1 do
        [if N >= Fib(I) then [N:= N-Fib(I);  ChOut(0, ^1);  LZ:= false]
        else ChOut(0, if LZ then ^  else ^0);
        ];
ChOut(0, N+^0);                 \output final digit, which can be 0
];

int N;
[for N:= 0 to 20 do
        [if N<10 then ChOut(0,^ );  IntOut(0, N);  Text(0, ": ");
        Zeckendorf(N);  CrLf(0);
        ];
]

Output:

zkl

    // return powers (0|1) of fib sequence (1,2,3,5,8...) that sum to n
fcn zeckendorf(n){ //-->String of 1s & 0s, no consecutive 1's
   if(n<=0) return("0");
   fibs:=fcn(ab){ ab.append(ab.sum()).pop(0) }.fp(L(1,2));
   (0).pump(*,List,fibs,'wrap(fib){ if(fib>n)Void.Stop else fib })
   .reverse()
   .pump(String,fcn(fib,rn){
      if(fib>rn.value)"0" else { rn.set(rn.value-fib); "1" } }.fp1(Ref(n)))
}

[0..20].pump(Console.println,fcn(n){ "%2d: %8s".fmt(n,zeckendorf(n)) });

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