Zeckendorf number representation: Difference between revisions

{{task}}

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.

 

 

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.

 

 

 

For $i = 0 To 20

ConsoleWrite($i &": "& Zeckendorf($i)&@CRLF)

Return $Array

EndFunc ;==>Fibonacci

'''Output:'''

<pre>

</pre>

 

PRINT n% RIGHT$(" " + FNzeckendorf(n%), 8)

NEXT

ENDIF

UNTIL i% = 1

'''Output:'''

<pre>

No Zeckendorf numbers contain consecutive 1's

</pre>

 

=={{header|C}}==

 

typedef unsigned long long u64;

 

return 0;

{{out}}

<pre>

19: 101001

20: 101010

</pre>

 

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

return os;

}

I may now write:

int main(void) {

//for (N G; G <= 101010N; ++G) std::cout << G << std::endl; // from zero to 101010M

return 0;

}

Which produces:

{{out}}

101010

</pre>

 

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

;;; task requirement

(loop for i from 0 to 20 do

 

;; Print Zeckendorf numbers upto 20.

;; I have implemented this as a state machine.

(if (= z 1) (format t "~S" 0)))))

(if (= z 0) (format t "~S~%" 0) (format t "~%"))))))

{{out}}

<pre>

19 is 101001

20 is 101010

</pre>

 

=={{header|D}}==

{{trans|Haskell}}

 

void main() {

{{out}}

<pre>0

 

{{trans|Go}}

 

int zeckendorf(in int n) pure nothrow {

foreach (i; 0 .. 21)

writefln("%2d: %6b", i, zeckendorf(i));

{{out}}

<pre> 0: 0

{{trans|Tcl}}

(Same output.)

 

string zeckendorf(size_t n) {

foreach (immutable i; 0 .. 21)

writefln("%2d: %6s", i, i.zeckendorf);

 

=={{header|Go}}==

 

import "fmt"

}

return

{{out}}

<pre> 0 0

=={{header|Haskell}}==

Using "no consecutive 1s" rule:

import Numeric

 

b x = showIntAtBase 2 ("01"!!) x ""

 

which is the same as

last s /= '1' || d /= '1']

 

or a different way to generate the sequence:

 

fib = 1 : 1 : zipWith (+) fib (tail fib)

b x = showIntAtBase 2 ("01"!!) x ""

 

 

Creating a string for an individual number:

 

zeckendorf 0 = "0"

 

{{out}}

<pre>

 

=={{header|J}}==

fib=: 3 : 0 " 0

mp=. +/ .*

 

phi=: -:1+%:5

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

fsum=: 3 : 0

z=. 0$r=. y

│100001│100010│100100│100101│101000│101001│101010│

└──────┴──────┴──────┴──────┴──────┴──────┴──────┘

 

=={{header|Java}}==

'''Code:'''

 

 

class Zeckendorf

System.out.println("Z(" + i + ")=" + getZeckendorf(i));

}

 

'''Output:'''

Z(19)=101001

Z(20)=101010</pre>

 

=={{header|Julia}}==

{{trans|Python}}

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

0

1

101000

101001

 

 

{{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|PARI/GP}}==

<pre>0

1

101010</pre>

 

 

{{out}}

 

=={{header|Python}}==

memo = [1, 2]

while True:

print('Fibonacci digit multipliers: %r' % sequence_down_from_n(n, fib))

for i in range(n + 1):

 

{{out}}

 

===Shorter version===

def z(n):

if n == 0 : return [0]

 

for i in range(n + 1):

{{out}}

19: 101001

20: 101010</pre>