Zeckendorf number representation: Difference between revisions
Zeckendorf number representation (view source)
Revision as of 13:29, 17 February 2024
, 3 months ago→{{header|Wren}}: Minor tidy
m (→{{header|Picat}}: subsections) |
m (→{{header|Wren}}: Minor tidy) |
||
(21 intermediate revisions by 13 users not shown) | |||
Line 28:
{{trans|Python}}
<
F z(=n)
I n == 0
Line 45:
L(i) 0..n
print(‘#3: #8’.format(i, z(i).map(d -> String(d)).join(‘’)))</
{{out}}
Line 74:
=={{header|360 Assembly}}==
{{trans|BBC BASIC}}
<
ZECKEN CSECT
USING ZECKEN,R13 base register
Line 140:
XDEC DS CL12 temp
YREGS
END ZECKEN</
{{out}}
<pre>
Line 167:
=={{header|Action!}}==
<
INT ARRAY fib(22)=
[1 2 3 5 8 13 21 34 55 89 144 233 377 610
Line 206:
PrintF("%I -> %S%E",i,s)
OD
RETURN</
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Zeckendorf_number_representation.png Screenshot from Atari 8-bit computer]
Line 235:
=={{header|Ada}}==
<
procedure Print_Zeck is
Line 260:
Ada.Text_IO.Put(To_String(Current) & " ");
end loop;
end Print_Zeck;</
{{out}}<pre>1 10 100 101 1000 1001 1010 10000 10001 10010 10100 10101 100000 100001 100010 100100 100101 101000 101001 101010</pre>
=={{header|ALGOL 68}}==
<
# We handle 32-bit numbers, the maximum fibonacci number that can fit in a #
Line 324:
print( ( whole( i, -3 ), " ", to zeckendorf( i ), newline ) )
OD
</syntaxhighlight>
{{out}}
<pre>
Line 353:
{{Trans|Haskell}} ('''mapAccumuL''' example)
<
-- zeckendorf :: Int -> String
Line 512:
end tell
return v
end |until|</
{{Out}}
<pre>0
Line 538:
=={{header|Arturo}}==
<
if x=0 -> return "0"
fib: new [2 1]
Line 559:
loop 0..20 'i ->
print [pad to :string i 3 pad Z i 8]</
{{out}}
Line 587:
=={{header|AutoHotkey}}==
{{works with|AutoHotkey_L}}
<
Loop, 21 {
i := A_Index - 1
Line 610:
}
return, a
}</
'''Output:'''
<pre>0: 0
Line 635:
=={{header|AutoIt}}==
<
For $i = 0 To 20
ConsoleWrite($i &": "& Zeckendorf($i)&@CRLF)
Line 678:
Return $Array
EndFunc ;==>Fibonacci
</syntaxhighlight>
'''Output:'''
<pre>
Line 704:
</pre>
=={{header|
==={{header|BBC BASIC}}===
<syntaxhighlight lang="bbcbasic"> FOR n% = 0 TO 20
PRINT n% RIGHT$(" " + FNzeckendorf(n%), 8)
NEXT
Line 731 ⟶ 732:
ENDIF
UNTIL i% = 1
= o$</
'''Output:'''
<pre>
Line 759 ⟶ 760:
No Zeckendorf numbers contain consecutive 1's
</pre>
==={{header|FreeBASIC}}===
<syntaxhighlight lang="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</syntaxhighlight>
{{out}}
<pre>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</pre>
==={{header|Liberty BASIC}}===
''CBTJD'': 2020/03/09
{{works with|Just BASIC}}
<syntaxhighlight lang="vb">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</syntaxhighlight>
{{out}}
<pre>
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
</pre>
==={{header|PureBasic}}===
<syntaxhighlight lang="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()</syntaxhighlight>
{{out}}
<pre> 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</pre>
==={{header|QuickBASIC}}===
{{trans|ALGOL 68}}
<syntaxhighlight lang="qbasic">
' 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
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
==={{header|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.
<syntaxhighlight lang="basic"> 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</syntaxhighlight>
{{out}}
<pre>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</pre>
==={{header|uBasic/4tH}}===
<syntaxhighlight lang="text">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()</syntaxhighlight>
Output:
<pre>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</pre>
==={{header|VBA}}===
{{trans|Phix}}<syntaxhighlight lang="vb">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</syntaxhighlight>{{out}}
<pre> 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</pre>
==={{header|VBScript}}===
<syntaxhighlight lang="vb">
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
</syntaxhighlight>
{{Out}}
<pre>
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
</pre>
==={{header|Yabasic}}===
<syntaxhighlight lang="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)
</syntaxhighlight>
=={{header|bc}}==
<syntaxhighlight lang="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)
}</syntaxhighlight>
{{out}}
<pre>0
1
10
100
101
1000
1001
1010
10000
10001
10010
10100
10101
100000
100001
100010
100100
100101
101000
101001
101010</pre>
=={{header|Befunge}}==
The first number on the stack, <tt>45*</tt>, 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.
<
v53210p 39+!:,,9+<
>858+37 *66g"7Y":v
Line 769 ⟶ 1,334:
^8:+1,+5_5<>-:0\`|
v:-\g39_^#:<*:p39<
>0\`:!"0"+#^ ,#$_^</
{{out}}
Line 795 ⟶ 1,360:
=={{header|C}}==
<
typedef unsigned long long u64;
Line 852 ⟶ 1,417:
return 0;
}</
{{out}}
<pre>
Line 879 ⟶ 1,444:
=={{header|C sharp}}==
<
using System;
using System.Collections.Generic;
Line 945 ⟶ 1,510:
}
}
</syntaxhighlight>
{{out}}
<pre>
Line 974 ⟶ 1,539:
{{works with|C++11}}
see [[Fibonacci sequence#Using Zeckendorf Numbers|Here]] for a further example using this class.
<
// For a class N which implements Zeckendorf numbers:
// I define an increment operation ++()
Line 1,010 ⟶ 1,575:
return os;
}
</syntaxhighlight>
I may now write:
<
int main(void) {
//for (N G; G <= 101010N; ++G) std::cout << G << std::endl; // from zero to 101010M
Line 1,018 ⟶ 1,583:
return 0;
}
</syntaxhighlight>
Which produces:
{{out}}
Line 1,042 ⟶ 1,607:
=={{header|Clojure}}==
<
(defn z [n]
Line 1,054 ⟶ 1,619:
(->> ps (reduce fz [[] n]) first (apply str)))))
(doseq [n (range 0 21)] (println n (z n)))</
=={{header|CLU}}==
<
fibonacci = proc (n: int) returns (array[int])
list: array[int] := array[int]$[]
Line 1,097 ⟶ 1,662:
stream$putl(po, zeckendorf(i))
end
end start_up</
{{out}}
<pre> 0: 0
Line 1,123 ⟶ 1,688:
=={{header|Common Lisp}}==
Common Lisp's arbitrary precision integers should handle any positive input:
<
"returns zeckendorf integer of n (see OEIS A003714)"
(let ((fib '(2 1)))
Line 1,137 ⟶ 1,702:
;;; 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.
Line 1,150 ⟶ 1,715:
(if (= z 1) (format t "~S" 0)))))
(if (= z 0) (format t "~S~%" 0) (format t "~%"))))))
</syntaxhighlight>
{{out}}
<pre>
Line 1,177 ⟶ 1,742:
=={{header|Cowgol}}==
<
sub zeckendorf(n: uint32, buf: [uint8]): (r: [uint8]) is
Line 1,221 ⟶ 1,786:
print_nl();
i := i + 1;
end loop;</
{{out}}
<pre>0: 0
Line 1,247 ⟶ 1,812:
=={{header|Crystal}}==
{{trans|Ruby of Python}}
<
return 0 if n.zero?
fib = [1, 2]
Line 1,262 ⟶ 1,827:
end
(0..20).each { |i| puts "%3d: %8d" % [i, zeckendorf(i)] }</
Using an explicit Iterator.
<
include Iterator(String)
Line 1,287 ⟶ 1,852:
end
zeckendorf(21).each_with_index{ |x,i| puts "%3d: %8s"% [i, x] }</
Using oneliners.
<
0.step.map(&.to_s(2)).reject(&.includes?("11")).first(n)
end
Line 1,300 ⟶ 1,865:
end
zeckendorf(21).each_with_index{ |x,i| puts "%3d: %8s"% [i, x] }</
{{out}}
Line 1,329 ⟶ 1,894:
=={{header|D}}==
{{trans|Haskell}}
<
void main() {
Line 1,338 ⟶ 1,903:
.take(21)
.binaryReverseArgs!writefln("%(%b\n%)");
}</
{{out}}
<pre>0
Line 1,363 ⟶ 1,928:
{{trans|Go}}
<
int zeckendorf(in int n) pure nothrow {
Line 1,384 ⟶ 1,949:
foreach (i; 0 .. 21)
writefln("%2d: %6b", i, zeckendorf(i));
}</
{{out}}
<pre> 0: 0
Line 1,410 ⟶ 1,975:
{{trans|Tcl}}
(Same output.)
<
string zeckendorf(size_t n) {
Line 1,430 ⟶ 1,995:
foreach (immutable i; 0 .. 21)
writefln("%2d: %6s", i, i.zeckendorf);
}</
=={{header|Dart}}==
{{trans|Java}}
<syntaxhighlight lang="Dart">
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();
}
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
<syntaxhighlight lang="Delphi">
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;
</syntaxhighlight>
{{out}}
<pre>
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.
</pre>
=={{header|EasyLang}}==
{{trans|FreeBASIC}}
<syntaxhighlight>
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
.
</syntaxhighlight>
=={{header|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)
Line 1,462 ⟶ 2,195:
(if ( > s n) 0
(begin (-= n s) 1 )))))))
</syntaxhighlight>
{{out}}
Line 1,476 ⟶ 2,209:
=={{header|Elena}}==
{{trans|C#}}
ELENA
<
import system'collections;
import system'text;
Line 1,505 ⟶ 2,238:
while (currentFibonaciNum <= num)
{
fibonacciNumbers.append
fibPosition := fibPosition + 1;
Line 1,514 ⟶ 2,247:
int temp := num;
fibonacciNumbers.sequenceReverse().forEach::(item)
{
if (item <= temp)
Line 1,533 ⟶ 2,266:
public program()
{
for(int i := 1
{
console.printFormatted("{0} : {1}",i,i.zeckendorf()).writeLine()
Line 1,539 ⟶ 2,272:
console.readChar()
}</
{{out}}
<pre>1 : 1
Line 1,565 ⟶ 2,298:
{{trans|Ruby}}
Stream generator:
<
def number do
Stream.unfold(0, fn n -> zn_loop(n) end)
Line 1,577 ⟶ 2,310:
Zeckendorf.number |> Enum.take(21) |> Enum.with_index
|> Enum.each(fn {zn, i} -> IO.puts "#{i}: #{zn}" end)</
{{out}}
Line 1,605 ⟶ 2,338:
Fibonacci numbers:
<
def number(n) do
fib_loop(n, [2,1])
Line 1,618 ⟶ 2,351:
end
for i <- 0..20, do: IO.puts "#{i}: #{Zeckendorf.number(i)}"</
same output
=={{header|Erlang}}==
{{trans|Elixir}}
<syntaxhighlight lang="Erlang">
% 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).
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|F_Sharp|F#}}==
<
let zeckendorf n =
Line 1,635 ⟶ 2,432:
|> List.rev
for i in 0 .. 20 do printfn "%2d: %8s" i (String.concat "" (zeckendorf i))</
{{out}}
<pre style="height:5em"> 0: 0
Line 1,660 ⟶ 2,457:
=={{header|Factor}}==
<
:: fib<= ( n -- seq )
Line 1,670 ⟶ 2,467:
[ dup s + n <= [ s + s! 49 ] [ drop 48 ] if ] "" map-as ;
21 <iota> [ dup zeck "%2d: %6s\n" printf ] each</
{{out}}
<pre>
Line 1,697 ⟶ 2,494:
=={{header|Forth}}==
<
>r 0 1 BEGIN dup r@ <= WHILE tuck + REPEAT drop rdrop ;
Line 1,711 ⟶ 2,508:
21 0 DO
cr i 2 .r tab i z.
LOOP ;</
{{out}}
<pre>
Line 1,749 ⟶ 2,546:
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 <code>F1B</code>, 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: <
Line 1,758 ⟶ 2,555:
The source uses F90 for its MODULE facility, in particular having array <code>F1B</code> 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 <code>:</code> there are secret additional parameters defining its size, accessible via special functions such as <code>UBOUND</code> 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.<
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.
Line 1,843 ⟶ 2,640:
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 <code>A</code> format code.
Line 1,873 ⟶ 2,670:
20 101010
</pre>
=={{header|Go}}==
<
import "fmt"
Line 2,000 ⟶ 2,702:
}
return
}</
{{out}}
<pre> 0 0
Line 2,026 ⟶ 2,728:
=={{header|Haskell}}==
Using "no consecutive 1s" rule:
<
import Numeric
Line 2,034 ⟶ 2,736:
b x = showIntAtBase 2 ("01"!!) x ""
main = mapM_ putStrLn $ take 21 zeckendorf</
which is the same as
<
last s /= '1' || d /= '1']
main = mapM putStrLn $ take 21 zeckendorf</
or a different way to generate the sequence:
<
fib = 1 : 1 : zipWith (+) fib (tail fib)
Line 2,051 ⟶ 2,753:
b x = showIntAtBase 2 ("01"!!) x ""
main = mapM_ putStrLn $ take 21 zeckendorf</
Creating a string for an individual number:
<
fib :: [Int]
Line 2,068 ⟶ 2,770:
main :: IO ()
main = (putStrLn . unlines) $ zeckendorf <$> [0 .. 20]</
{{out}}
<pre>
Line 2,096 ⟶ 2,798:
=={{header|J}}==
Please enjoy our [http://www.jsoftware.com/jwiki/Essays/Fibonacci%20Sums Zeckendorf essay].
<syntaxhighlight lang="j">
fib=: 3 : 0 " 0
mp=. +/ .*
Line 2,126 ⟶ 2,828:
│100001│100010│100100│100101│101000│101001│101010│
└──────┴──────┴──────┴──────┴──────┴──────┴──────┘
</syntaxhighlight>
Explanation:
Line 2,142 ⟶ 2,844:
'''Code:'''
<
class Zeckendorf
Line 2,174 ⟶ 2,876:
System.out.println("Z(" + i + ")=" + getZeckendorf(i));
}
}</
'''Output:'''
Line 2,203 ⟶ 2,905:
'''Code:'''
<
import java.util.List;
Line 2,243 ⟶ 2,945:
}
}
}</
'''Output:'''
Line 2,272 ⟶ 2,974:
===ES6===
{{Trans|Haskell}} ('''mapAccumuL''' example)
<
'use strict';
Line 2,406 ⟶ 3,108:
// MAIN ---
return main();
})();</
{{Out}}
<pre>0
Line 2,432 ⟶ 3,134:
=={{header|jq}}==
{{works with|jq|1.5}}
<
def fibs($n):
# input: [f(i-2), f(i-1)]
Line 2,456 ⟶ 3,158:
| [., ($f|length)-1]
| loop($f)
| join("") ;</
'''Example:'''
<
{{out}}
<
0: 0
1: 1
Line 2,482 ⟶ 3,184:
18: 101000
19: 101001
20: 101010</
=={{header|Julia}}==
{{trans|Python}}
<
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</
{{out}}
<pre>
Line 2,521 ⟶ 3,223:
=={{header|Klingphix}}==
<
:listos
Line 2,547 ⟶ 3,249:
20 Zeckendorf
nl "End " input</
{{out}}
<pre>0: 0
Line 2,574 ⟶ 3,276:
=={{header|Kotlin}}==
<
const val LIMIT = 46 // to stay within range of signed 32 bit integer
Line 2,612 ⟶ 3,314:
println(" n z")
for (i in 0..20) println("${"%2d".format(i)} : ${zeckendorf(i)}")
}</
{{out}}
Line 2,639 ⟶ 3,341:
20 : 101010
</pre>
=={{header|Lingo}}==
{{trans|Lua}}
<
on fibsUpTo (n)
fibList = []
Line 2,700 ⟶ 3,372:
if zeck = "" then return "0"
return zeck
end</
<
put n & ": " & zeckendorf(n)
end repeat</
{{out}}
Line 2,735 ⟶ 3,407:
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.
<syntaxhighlight lang="little man computer">
// Little Man Computer, for Rosetta Code.
// Writes Zeckendorf representations of numbers 0..20.
Line 2,815 ⟶ 3,487:
ascii_1 DAT 49
// end
</syntaxhighlight>
{{out}}
<pre>
Line 2,844 ⟶ 3,516:
=={{header|Logo}}==
<
to fib m
local "n
Line 2,894 ⟶ 3,566:
]
print []
bye</
{{Out}}
<pre>0 1 10 100 101 1000 1001 1010 10000 10001 10010 10100 10101 100000 100001 100010 100100 100101 101000 101001 101010</pre>
=={{header|Lua}}==
<
function fibsUpTo (n)
local fibList, last, current, nxt = {}, 1, 1
Line 2,931 ⟶ 3,603:
for n = 0, 20 do
print(" " .. n, "| " .. zeckendorf(n))
end</
{{out}}
<pre> n | Zeckendorf(n)
Line 2,958 ⟶ 3,630:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">
ZeckendorfRepresentation[0] = 0;
ZeckendorfRepresentation[n_Integer?Positive]:=
NumberDecompose[n, Reverse@Fibonacci@Range[2,1000]] // FromDigits
{{Out}}
<pre>{0, 1, 10, 100, 101, 1000, 1001, 1010, 10000, 10001, 10010, 10100,
10101, 100000, 100001, 100010, 100100, 100101, 101000, 101001, 101010}</pre>
=={{header|MATLAB}}==
{{trans|Julia}}
<syntaxhighlight lang="MATLAB">
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
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|MiniScript}}==
<syntaxhighlight lang="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
</syntaxhighlight>
{{out}}
<pre>[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"]
</pre>
=={{header|Nim}}==
{{trans|Python}}
<
proc z(n: Natural): string =
Line 2,988 ⟶ 3,778:
for i in 0 .. 20:
echo &"{i:>3} {z(i):>8}"</
{{out}}
Line 3,012 ⟶ 3,802:
19 101001
20 101010</pre>
=={{header|OCaml}}==
<syntaxhighlight lang="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</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|PARI/GP}}==
<
for(n=0,20,Z(n))</
<pre>0
1
Line 3,041 ⟶ 3,871:
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;
Line 3,093 ⟶ 3,923:
WriteLn( SysUtils.Format( '%2d: %s', [C, ZeckRep(C)]));
end.
</syntaxhighlight>
{{out}}
<pre>
Line 3,120 ⟶ 3,950:
=={{header|Perl}}==
<
sub fib {
Line 3,143 ⟶ 3,973:
printf "%4d: %8s\n", $_, zeckendorf($_) for 0..20;
</syntaxhighlight>
{{out}}
<pre> 0: 0
Line 3,169 ⟶ 3,999:
=={{header|Phix}}==
<!--<
<span style="color: #008080;">function</span> <span style="color: #000000;">zeckendorf</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">c</span>
Line 3,187 ⟶ 4,017:
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%2d: %7b\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">zeckendorf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</
{{Out}}
<pre>
Line 3,214 ⟶ 4,044:
=={{header|Phixmonti}}==
<
0 var i 0 var c 1 1 2 tolist var pattern
true
Line 3,234 ⟶ 4,064:
enddef
20 Zeckendorf</
=={{header|PHP}}==
<syntaxhighlight lang="php">
<?php
$m = 20;
Line 3,260 ⟶ 4,090:
}
?>
</syntaxhighlight>
{{out}}
<pre>
Line 3,287 ⟶ 4,117:
=={{header|Picat}}==
===Constraint model===
<
foreach(Num in 0..20)
zeckendorf_cp(Num,X,F),
Line 3,347 ⟶ 4,177:
Fibs1 := Fibs1 ++ [Fib]
end,
Fibs = Fibs1.</
{{out}}
Line 3,373 ⟶ 4,203:
===An iterative approach===
<
foreach(Num in 0..20)
zeckendorf2(Num,X,F),
Line 3,396 ⟶ 4,226:
end,
X = X1,
F = Fibs.reverse().</
=={{header|PicoLisp}}==
<
(let Fibs (1 1)
(while (>= N (+ (car Fibs) (cadr Fibs)))
Line 3,429 ⟶ 4,259:
(glue " + " (zecken2 N)) ) )
(bye)</
{{out}}
<pre>
Line 3,457 ⟶ 4,287:
This code needs an etex engine.
<
\let\fibolist\empty\def\targetsum{#1}\def\fibosum{0}%
\genfibolistaux1,1\relax
Line 3,493 ⟶ 4,323:
}
\listzeckendorf{20}% any integer accepted
\bye</
pdf output looks like:
Line 3,521 ⟶ 4,351:
=={{header|PowerShell}}==
{{works with|PowerShell|2}}
<syntaxhighlight lang="powershell">
function Get-ZeckendorfNumber ( $N )
{
Line 3,548 ⟶ 4,378:
return $ZeckendorfNumber
}
</syntaxhighlight>
<syntaxhighlight lang="powershell">
# Get Zeckendorf numbers through 20, convert to binary for display
0..20 | ForEach { [convert]::ToString( ( Get-ZeckendorfNumber $_ ), 2 ) }
</syntaxhighlight>
{{out}}
<pre>
Line 3,577 ⟶ 4,407:
101010
</pre>
=={{header|Python}}==
<
memo = [1, 2]
while True:
Line 3,663 ⟶ 4,442:
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))))</
{{out}}
Line 3,690 ⟶ 4,469:
===Shorter version===
<
def z(n):
if n == 0 : return [0]
Line 3,704 ⟶ 4,483:
for i in range(n + 1):
print('%3i: %8s' % (i, ''.join(str(d) for d in z(i))))</
{{out}}
Line 3,733 ⟶ 4,512:
Converting non-negative integers to and from Zeckendorf representation.
<
echo
base release ] is binecho ( n --> )
Line 3,766 ⟶ 4,545:
21 times
[ i^ dup echo
say " -> "
n->z dup binecho
say " -> "
z->n echo cr ]</
{{Out}}
Line 3,796 ⟶ 4,575:
=={{header|R}}==
<
# Get an upper limit on Fibonacci numbers needed to cover number
Line 3,839 ⟶ 4,618:
}
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.
Line 3,849 ⟶ 4,628:
=={{header|Racket}}==
<
#lang racket (require math)
Line 3,867 ⟶ 4,646:
(for/list ([n 21])
(list n (zechendorf n)))
</syntaxhighlight>
Output:
<
'((0 ())
(1 (1))
Line 3,891 ⟶ 4,670:
(19 (1 0 1 0 0 1))
(20 (1 0 1 0 1 0)))
</syntaxhighlight>
=={{header|Raku}}==
(formerly Perl 6)
{{Works with|rakudo|2015.12}}
<syntaxhighlight lang="raku"
multi zeckendorf(0) { '0' }
Line 3,905 ⟶ 4,684:
+$digit;
}, reverse FIBS ...^ * > $n;
}</
{{out}}
<pre> 0: 0
Line 3,931 ⟶ 4,710:
=={{header|REXX}}==
===specific to 20===
<
/* REXX ***************************************************************
* 11.10.2012 Walter Pachl
Line 3,953 ⟶ 4,732:
If r='' Then r='0' /* take care of 0 */
Say right(n,2)': 'right(r,6) /* show result */
End</
Output:
<pre>
Line 3,981 ⟶ 4,760:
This generalized REXX version will work for any Zeckendorf number (up to 100,000 decimal digits).
<br><br>A list of Fibonacci numbers (in ascending order) is generated large enough to handle the '''N<sup>th</sup>''' Zeckendorf number.
<
numeric digits 100000 /*just in case user gets real ka─razy. */
parse arg N . /*let the user specify the upper limit.*/
Line 3,998 ⟶ 4,777:
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. */</
{{out|output|text= when using the default input:}}
<pre>
Line 4,029 ⟶ 4,808:
There isn't any need to generate a Fibonacci series with this method. This method is extremely fast.
<
numeric digits 100000 /*just in case user gets real ka─razy. */
parse arg N . /*let the user specify the upper limit.*/
Line 4,038 ⟶ 4,817:
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. */</
{{out|output|text= is identical to the previous (generalized) version.}} <br><br>
=={{header|Ring}}==
<
# Project : Zeckendorf number representation
Line 4,070 ⟶ 4,849:
end
return o
</syntaxhighlight>
Output:
<pre>
Line 4,095 ⟶ 4,874:
20 101010
</pre>
=={{header|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|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
{{out}}
<pre>
{ "1" "10" "100" "101" "1000" "1001" "1010" "10000" "10001" "10010" "10100" "10101" "100000" "100001" "100010" "100100" "100101" "101000" "101001" "101010" }
</pre>
=={{header|Ruby}}==
Featuring a method doubling as an enumerator.
<
return to_enum(__method__) unless block_given?
x = 0
Line 4,108 ⟶ 4,917:
end
zeckendorf.take(21).each_with_index{|x,i| puts "%3d: %8s"% [i, x]}</
{{trans|Python}}
<
return 0 if n.zero?
fib = [1,2]
Line 4,128 ⟶ 4,937:
for i in 0..20
puts '%3d: %8d' % [i, zeckendorf(i)]
end</
As oneliner.
{{trans|Crystal}}
<
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] }
</syntaxhighlight>
{{out}}
Line 4,161 ⟶ 4,970:
19: 101001
20: 101010</pre>
=={{header|Rust}}==
{{trans|C#}}
<syntaxhighlight lang="Rust">
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);
}
}
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|Scala}}==
<
if( n == 0 ) return "0" // Short-circuit this and return zero if we were given zero
Line 4,192 ⟶ 5,072:
// A little test...
(0 to 20) foreach( i => print( zNum(i) + "\n" ) )
</syntaxhighlight>
{{out}}
<pre>0
Line 4,219 ⟶ 5,099:
=={{header|Scheme}}==
{{trans|Java}}
<
(define (getFibList maxNum n1 n2 fibs)
Line 4,249 ⟶ 5,129:
(newline)
(loop (+ i 1))))
</syntaxhighlight>
{{out}}
<pre>Z(0): 0
Line 4,275 ⟶ 5,155:
=={{header|Sidef}}==
{{trans|Perl}}
<
n < 2 ? 1
: (fib(n-1) + fib(n-2))
Line 4,295 ⟶ 5,175:
for n (0..20) {
printf("%4d: %8s\n", n, zeckendorf(n))
}</
{{out}}
<pre>
Line 4,323 ⟶ 5,203:
=={{header|Simula}}==
{{trans|Sinclair ZX81 BASIC}}
<
INTEGER N, F0, F1, F2, D;
N := 20;
Line 4,359 ⟶ 5,239:
END; ! 230 next i ;
END;
END</
{{out}}
<pre>0 0
Line 4,432 ⟶ 5,264:
=={{header|Standard ML}}==
<syntaxhighlight lang="standard ml">
val zeckList = fn from => fn to =>
Line 4,466 ⟶ 5,298:
Zeck ( from + (fromInt i) )))
end;
</syntaxhighlight>
output
<syntaxhighlight lang="standard ml">
List.app ( fn e => print ( (IntInf.toString (#1 e)) ^" : "^ (IntInf.toString (#2 e)) ^ "\n" )) (zeckList 1 21) ;
1 : 1
Line 4,494 ⟶ 5,326:
val it = [(568533155, 100100100101001001001000000100100010100101)]:
: (IntInf.int * IntInf.int) list
</syntaxhighlight>
=={{header|Tcl}}==
<
# Generates the Fibonacci sequence (starting at 1) up to the largest item that
Line 4,525 ⟶ 5,357:
}
return [join $zs ""]
}</
Demonstration
<
puts [format "%2d:%9s" $i [zeckendorf $i]]
}</
{{out}}
<pre> 0: 0
Line 4,553 ⟶ 5,385:
20: 101010</pre>
=={{header|
<syntaxhighlight lang="sh">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</syntaxhighlight>
{{out}}
<pre>0: 0
1: 1
2: 10
Line 4,715 ⟶ 5,419:
18: 101000
19: 101001
20: 101010</pre>
=={{header|V (Vlang)}}==
{{trans|Go}}
<syntaxhighlight lang="v (vlang)">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
}</syntaxhighlight>
{{out}}
<pre>
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
</pre>
Line 4,721 ⟶ 5,482:
{{trans|Kotlin}}
{{libheader|Wren-fmt}}
<
var LIMIT = 46 // to stay within range of signed 32 bit integer
Line 4,759 ⟶ 5,520:
System.print(" n z")
for (i in 0..20) Fmt.print("$2d : $s", i, zeckendorf.call(i))</
{{out}}
Line 4,788 ⟶ 5,549:
=={{header|XPL0}}==
<
proc Zeckendorf(N); \Display Zeckendorf number (N <= 20)
Line 4,807 ⟶ 5,568:
Zeckendorf(N); CrLf(0);
];
]</
Output:
Line 4,833 ⟶ 5,594:
20: 101010
</pre>
=={{header|zkl}}==
<
fcn zeckendorf(n){ //-->String of 1s & 0s, no consecutive 1's
if(n<=0) return("0");
Line 4,861 ⟶ 5,604:
.pump(String,fcn(fib,rn){
if(fib>rn.value)"0" else { rn.set(rn.value-fib); "1" } }.fp1(Ref(n)))
}</
<
{{out}}
<pre style="height:7em">
Line 4,888 ⟶ 5,631:
</pre>
{{omit from|PL/0}}
{{omit from|Tiny BASIC}}
[[Category: Bitwise operations]]
|