Zeckendorf number representation: Difference between revisions
(→{{header|Kotlin}}: Updated example see https://github.com/dkandalov/rosettacode-kotlin for details) |
PatGarrett (talk | contribs) (→{{header|360 Assembly}}: Section added) |
||
| Line 24: | Line 24: | ||
* [[Fibonacci sequence]] |
* [[Fibonacci sequence]] |
||
<br><br> |
<br><br> |
||
=={{header|360 Assembly}}== |
|||
{{trans|BBC BASIC}}<lang 360asm> |
|||
* 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</lang> |
|||
{{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|Ada}}== |
=={{header|Ada}}== |
||
Revision as of 12:31, 4 April 2017
You are encouraged to solve this task according to the task description, using any language you may know.
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
360 Assembly
<lang 360asm>
- 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</lang>
- 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
Ada
<lang 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;</lang>
- Output:
1 10 100 101 1000 1001 1010 10000 10001 10010 10100 10101 100000 100001 100010 100100 100101 101000 101001 101010
ALGOL 68
<lang algol68># 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 </lang>
- 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
AppleScript
(mapAccumuL example)
<lang AppleScript>-- zeckendorf :: Int -> String on zeckendorf(n)
script f
on lambda(n, x)
if n < x then
[n, 0]
else
[n - x, 1]
end if
end lambda
end script
if n = 0 then
{0} as string
else
item 2 of mapAccumL(f, n, _reverse(tail(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 lambda(x)
(item 2 of x) > (atLimit's ceiling)
end lambda
end script
script nextPair
property series : xs
on lambda([a, b])
set nextPair's series to nextPair's series & b
[b, a + b]
end lambda
end script
|until|(atLimit, nextPair, {0, 1})
return nextPair's series
end fibUntil
-- TEST
on run
intercalate(linefeed, ¬
map(zeckendorf, range(0, 20)))
end run
-- GENERIC LIBRARY FUNCTIONS
-- '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 lambda(a, x)
tell mReturn(f) to set pair to lambda(item 1 of a, x)
[item 1 of pair, (item 2 of a) & item 2 of pair]
end lambda
end script
foldl(result, [acc, []], xs)
end mapAccumL
-- 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 lambda(v)
set v to lambda(v)
end repeat
end tell
return v
end |until|
-- 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 lambda(item i of xs, i, xs)
end repeat
return lst
end tell
end map
-- 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 lambda(v, item i of xs, i, xs)
end repeat
return v
end tell
end foldl
-- 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 lambda : f
end script
end if
end mReturn
-- range :: Int -> Int -> [Int] on range(m, n)
if n < m 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 range
-- 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
-- tail :: [a] -> [a] on tail(xs)
if length of xs > 1 then
items 2 thru -1 of xs
else
{}
end if
end tail</lang>
- Output:
0 1 10 100 101 1000 1001 1010 10000 10001 10010 10100 10101 100000 100001 100010 100100 100101 101000 101001 101010
AutoHotkey
<lang AutoHotkey>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 }</lang>NStepSequence() 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
AutoIt
<lang 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 </lang> 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
BBC BASIC
<lang bbcbasic> 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$</lang>
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
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.
<lang befunge>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"+#^ ,#$_^</lang>
- 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
<lang 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; }</lang>
- 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 a C++11 User Defined Literal
see Here for a further example using this class. <lang cpp> // 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;
} </lang> I may now write: <lang cpp> 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;
} </lang> Which produces:
- Output:
101 1000 1001 1010 10000 10001 10010 10100 10101 100000 100001 100010 100100 100101 101000 101001 101010
C#
<lang csharp> 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();
}
}
} </lang>
- 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
Clojure
<lang 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)))</lang>
Common Lisp
Common Lisp's arbitrary precision integers should handle any positive input: <lang lisp>(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)))</lang>
<lang lisp>
- 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 "~%"))))))
</lang>
- 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
D
<lang d>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%)");
}</lang>
- Output:
0 1 10 100 101 1000 1001 1010 10000 10001 10010 10100 10101 100000 100001 100010 100100 100101 101000 101001 101010
<lang d>import std.stdio, std.typecons;
int zeckendorf(in int n) pure nothrow {
Tuple!(int,"remaining", int,"set")
zr(in int fib0, in int fib1, in int n, in uint bit) pure nothrow {
if (fib1 > n)
return typeof(return)(n, 0);
auto rs = zr(fib1, fib0 + fib1, n, bit + 1);
if (fib1 <= rs.remaining) {
rs.set |= 1 << bit;
rs.remaining -= fib1;
}
return rs;
}
return zr(1, 1, n, 0)[1];
}
void main() {
foreach (i; 0 .. 21)
writefln("%2d: %6b", i, zeckendorf(i));
}</lang>
- 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
(Same output.) <lang d>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);
}</lang>
EchoLisp
We analytically find the first fibonacci(i) >= n, using the formula i = log((n* Φ) + 0.5) / log(Φ) . <lang scheme>
- 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 )))))))
</lang>
- 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
Elixir
Stream generator: <lang elixir>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)</lang>
- 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
Fibonacci numbers: <lang elixir>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)}"</lang> same output
F#
<lang fsharp>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))</lang>
- 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
Forth
<lang 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 ;</lang>
- 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
FreeBASIC
<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</lang>
- 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
Go
<lang 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
}</lang>
- 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
Haskell
Using "no consecutive 1s" rule: <lang haskell>import Data.Bits import Numeric
zeckendorf = map b $ filter ones [0..] where ones :: Int -> Bool ones x = 0 == x .&. (x `shiftR` 1) b x = showIntAtBase 2 ("01"!!) x ""
main = mapM_ putStrLn $ take 21 zeckendorf</lang> which is the same as <lang haskell>zeckendorf = "0":"1":[s++[d] | s <- tail zeckendorf, d <- "01", last s /= '1' || d /= '1']
main = mapM putStrLn $ take 21 zeckendorf</lang> or a different way to generate the sequence: <lang haskell>import Numeric
fib = 1 : 1 : zipWith (+) fib (tail fib) pow2 = iterate (2*) 1
zeckendorf = map b z where z = 0:concat (zipWith f fib pow2) f x y = map (y+) (take x z) b x = showIntAtBase 2 ("01"!!) x ""
main = mapM_ putStrLn $ take 21 zeckendorf</lang>
Creating a string for an individual number: <lang haskell>import Data.List (mapAccumL)
fib = 1 : 2 : zipWith (+) fib (tail fib)
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 = mapM_ (putStrLn . zeckendorf) [0..20]</lang>
- Output:
0 1 10 100 101 1000 1001 1010 10000 10001 10010 10100 10101 100000 100001 100010 100100 100101 101000 101001 101010
J
Please enjoy our Zeckendorf essay. <lang J> 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│ └──────┴──────┴──────┴──────┴──────┴──────┴──────┘ </lang>
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:
<lang java>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));
}
}</lang>
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: <lang java>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>()Template: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));
}
}
}</lang>
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
(mapAccumuL example)
<lang JavaScript>(() => {
'use strict';
// zeckendorf :: Int -> String
function zeckendorf(n) {
let f = (n, x) => (n < x ? [n, 0] : [n - x, 1]);
return (n === 0 ? (
[0]
) : mapAccumL(f, n, reverse(tail(fibUntil(n))))[1])
.join();
}
// fibUntil :: Int -> [Int]
let fibUntil = n => {
let xs = [];
until(
([a, b]) => a > n,
([a, b]) => (xs.push(a), [b, a + b]), [1, 1]
)
return xs;
}
// GENERIC FUNCTIONS
// mapAccumL :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y])
let mapAccumL = (f, acc, xs) => {
return xs.reduce((a, x) => {
let pair = f(a[0], x);
return [pair[0], a[1].concat(pair[1])];
}, [acc, []]);
}
// until :: (a -> Bool) -> (a -> a) -> a -> a
let until = (p, f, x) => {
let v = x;
while (!p(v)) v = f(v);
return v;
}
// tail :: [a] -> [a] let tail = xs => xs.length ? xs.slice(1) : undefined;
// reverse :: [a] -> [a]
let reverse = xs => xs.slice(0)
.reverse();
// range :: Int -> Int -> [Int]
let range = (m, n) =>
Array.from({
length: Math.floor(n - m) + 1
}, (_, i) => m + i);
// TEST
return range(0, 20)
.map(zeckendorf)
.join('\n')
})(); </lang>
- Output:
0 1 10 100 101 1000 1001 1010 10000 10001 10010 10100 10101 100000 100001 100010 100100 100101 101000 101001 101010
jq
<lang jq>def zeckendorf:
# rfibs(n) returns an array of fibonnaci numbers up to n,
# beginning with 1, 2, ..., in reverse order
def rfibs(n):
# input: [f(i-2), f(i-1)]
[1,1] | [recurse( if .[1] >= n then empty
else [.[1], add]
end ) | .[1]] | reverse;
. as $n
# [n, rfibs, digit ]
| [$n, rfibs($n), "" ]
| [ recurse( .[0] as $n | .[1] as $f
| if ($f|length) == 0 then empty
else
$f[0] as $next
| if $n >= $next then [ ( $n - $next), $f[1:], "1"]
else [ $n, $f[1:], "0"]
end
end )
| .[2] ]
| if .[1] == "0" then .[2:] else . end # remove leading 0 if any
| join("") ;</lang>
Example: <lang jq>range(0;21) | "\(.): \(zeckendorf)"</lang>
- Output:
<lang sh>$ jq -n -r -f zeckendorf.jq 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</lang>
Julia
<lang julia>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</lang>
- 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
Kotlin
<lang scala>// 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)}")
}</lang>
- 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
Logo
<lang 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</lang>
- Output:
0 1 10 100 101 1000 1001 1010 10000 10001 10010 10100 10101 100000 100001 100010 100100 100101 101000 101001 101010
Lua
<lang 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</lang>
- 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
<lang Mathematica>zeckendorf[0] = 0; zeckendorf[n_Integer] :=
10^(# - 1) + zeckendorf[n - Fibonacci[# + 1]] &@
LengthWhile[
Fibonacci /@
Range[2, Ceiling@Log[GoldenRatio, n Sqrt@5]], # <= n &];
zeckendorf /@ Range[0, 20]</lang>
- Output:
{0, 1, 10, 100, 101, 1000, 1001, 1010, 10000, 10001, 10010, 10100,
10101, 100000, 100001, 100010, 100100, 100101, 101000, 101001, 101010}
Nim
<lang nim>import strutils
proc z(n): string =
if n == 0: return "0"
var fib = @[2,1]
var n = n
while fib[0] < n: fib.insert(fib[0] + fib[1])
result = ""
for f in fib:
if f <= n:
result.add '1'
n -= f
else:
result.add '0'
if result[0] == '0':
result = result[1..result.high]
for i in 0 .. 20:
echo align($i, 3)," ",align(z(i), 8)</lang>
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
<lang parigp>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))</lang>
0 1 10 100 101 1000 1001 1010 10000 10001 10010 10100 10101 100000 100001 100010 100100 100101 101000 101001 101010
Perl
<lang 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; </lang>
- 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
Perl 6
<lang perl6>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;
}</lang>
- 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
PHP
<lang 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";
} ?> </lang>
- Output:
20: 101010 19: 101001 18: 101000 17: 100101 16: 100100 15: 100010 14: 100001 13: 100000 12: 10101 11: 10100 10: 10010 9: 10001 8: 10000 7: 1010 6: 1001 5: 1000 4: 101 3: 100 2: 10 1: 1
PicoLisp
<lang 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)</lang>
- 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 TeX
This code needs an etex engine.
<lang tex>\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</lang>
pdf output looks like:
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
PowerShell
<lang PowerShell> 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
}
</lang> <lang PowerShell>
- Get Zeckendorf numbers through 20, convert to binary for display
0..20 | ForEach { [convert]::ToString( ( Get-ZeckendorfNumber $_ ), 2 ) } </lang>
- Output:
0 1 10 100 101 1000 1001 1010 10000 10001 10010 10100 10101 100000 100001 100010 100100 100101 101000 101001 101010
Python
<lang 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))))</lang>
- 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
<lang python>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))))</lang>
- 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
R
<lang 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)))</lang>
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>
- 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)))
</lang> Output: <lang racket> '((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)))
</lang>
REXX
specific to 20
<lang rexx> /* 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</lang>
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 Nth Zeckendorf number.
<lang rexx>/*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. */</lang>
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 Nth Zeckendorf numbers (up to 100,000 decimal digits) by
using binary numbers that don't have two consecutive 11s within their binary version.
There is no need to generate a Fibonacci series with this method. This method is extremely fast. <lang REXX>/*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*/ /* [↑] compute/display Zeckendorf #s. */
/*stick a fork in it, we're all done. */</lang>
output is identical to the previous (generalized) version.
Ruby
Featuring a method doubling as an enumerator. <lang ruby>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]} </lang>
- 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
<lang ruby>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</lang> (Same output.)
Scala
<lang 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" ) )
</lang>
- Output:
0 1 10 100 101 1000 1001 1010 10000 10001 10010 10100 10101 100000 100001 100010 100100 100101 101000 101001 101010
Sidef
<lang ruby>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();
}
range(0, 20).each { |n|
printf("%4d: %8s\n", n, zeckendorf(n))
}</lang>
- 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
Tcl
<lang tcl>package require Tcl 8.5
- Generates the Fibonacci sequence (starting at 1) up to the largest item that
- is no larger than the target value. Could use tricks to precompute, but this
- is actually a pretty cheap linear operation.
proc fibseq target {
set seq {}; set prev 1; set fib 1
for {set n 1;set i 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 ""]
}</lang> Demonstration <lang tcl>for {set i 0} {$i <= 20} {incr i} {
puts [format "%2d:%9s" $i [zeckendorf $i]]
}</lang>
- 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
uBasic/4tH
<lang>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()</lang>
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
VBScript
<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 </lang>
- 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
XPL0
<lang 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);
];
]</lang>
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
zkl
<lang 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)))
}</lang> <lang zkl>[0..20].pump(Console.println,fcn(n){ "%2d: %8s".fmt(n,zeckendorf(n)) });</lang>
- 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
- Programming Tasks
- Solutions by Programming Task
- 360 Assembly
- Ada
- ALGOL 68
- AppleScript
- AutoHotkey
- AutoIt
- BBC BASIC
- Befunge
- C
- C++
- C sharp
- Clojure
- Common Lisp
- D
- EchoLisp
- Elixir
- F Sharp
- Forth
- FreeBASIC
- Go
- Haskell
- J
- Java
- JavaScript
- Jq
- Julia
- Kotlin
- Logo
- Lua
- Mathematica
- Nim
- PARI/GP
- Perl
- Perl 6
- PHP
- PicoLisp
- PlainTeX
- PowerShell
- Python
- R
- Racket
- REXX
- Ruby
- Scala
- Sidef
- Tcl
- UBasic/4tH
- VBScript
- XPL0
- Zkl
- Bitwise operations