Zeckendorf number representation: Difference between revisions
m (→{{header|REXX}}: removed STYLE from the PRE html tag.) |
m (→generic: changed a DO-END index comment.) |
||
Line 1,548: | Line 1,548: | ||
say ' Zeckendorf' right(z,length(n)) '= ' right(_+0,30) /*show #.*/ |
say ' Zeckendorf' right(z,length(n)) '= ' right(_+0,30) /*show #.*/ |
||
z=z+1 /*bump the Zeckendorf # counter.*/ |
z=z+1 /*bump the Zeckendorf # counter.*/ |
||
end /* |
end /*j*/ /* [↑] compute/show Zeckendorf #s*/ |
||
/*stick a fork in it, we're done.*/</lang> |
/*stick a fork in it, we're done.*/</lang> |
||
'''output''' is the same as the previous (generalized) version. |
'''output''' is the same as the previous (generalized) version. |
Revision as of 04:56, 23 November 2014
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.
The task is to generate and show here a table of the Zeckendorf number representations of the decimal numbers zero to twenty, in order. See OEIS A014417 for the the sequence of required results. Cf:
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.
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
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
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>
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
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>
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
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
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}
Nimrod
<lang nimrod>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, *+* ... *; [~] 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
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 1,000 digits).
A list of Fibonacci numbers (in ascending order) is generated large enough to handle the Nth Zeckendorf number.
<lang rexx>/*REXX pgm calculates and displays the first N Zeckendorf numbers. */
numeric digits 1000 /*just in case user gets ka-razy.*/
parse arg n .; if n== then n=20 /*let user specify upper limit. */
- =1 2; do until word(#,words(#))>n /*build a list of Fib numbers. */
w=words(#) /*number of words in list of Fib#*/ #=# (word(#,w-1)+word(#,w)) /*sum the last two Fib numbers. */ end /*until word(#, ··· */
do j=0 to n; parse var j x z /*task: process zero ──► N */ do k=w by -1 for w; _=word(#,k) /*process all the Fibonacci nums.*/ if x>=_ then do /*is X>than the next Fib number? */ z=z'1' /* ··· then append unity (1). */ x=x-_ /*subtract this fib# from index. */ end else z=z'0' /* append zero (0). */ end /*k*/ say ' Zeckendorf' right(j,length(n)) '= ' right(z+0,30) /*show #*/ end /*j*/ /*stick a fork in it, we're 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 N Zeckendorf numbers (up to 1,000 digits) by
using binary numbers that don't have two consecutive 11s in them.
There is no need to generate a Fibonacci series with this method.
<lang REXX>/*REXX pgm calculates and displays the first N Zeckendorf numbers. */
numeric digits 1000 /*just in case user gets ka─razy.*/
parse arg n .; if n== then n=20 /*let user specify upper limit. */
z=0 /*index of a Zeckendorf number. */
do j=0 until z>n; _=x2b(d2x(j)) /*task: process zero ──► N. */ if pos(11,_)\==0 then iterate /*two consecutive ones (1s) ? */ say ' Zeckendorf' right(z,length(n)) '= ' right(_+0,30) /*show #.*/ z=z+1 /*bump the Zeckendorf # counter.*/ end /*j*/ /* [↑] compute/show Zeckendorf #s*/ /*stick a fork in it, we're done.*/</lang>
output is the same as 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
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
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