A139764 Smallest term in Zeckendorf representation of n.

1, 2, 3, 1, 5, 1, 2, 8, 1, 2, 3, 1, 13, 1, 2, 3, 1, 5, 1, 2, 21, 1, 2, 3, 1, 5, 1, 2, 8, 1, 2, 3, 1, 34, 1, 2, 3, 1, 5, 1, 2, 8, 1, 2, 3, 1, 13, 1, 2, 3, 1, 5, 1, 2, 55, 1, 2, 3, 1, 5, 1, 2, 8, 1, 2, 3, 1, 13, 1, 2, 3, 1, 5, 1, 2, 21, 1, 2, 3, 1, 5, 1, 2, 8, 1, 2, 3, 1, 89

Offset: 1

Author

Steve Witham (sw(AT)tiac.net), May 15 2008

Keywords

• nonn
• nice

Comments

Also called a "Fibonacci fractal".

Appears to be the same as the "ruler of Fibonaccis" mentioned by Knuth. - N. J. A. Sloane, Aug 03 2012

a(n) is also the number of matches to take away to win in a certain match game (see Rocher et al.).

The frequencies of occurrences of the values in this sequence and A035614 are related by the golden ratio.

Examples

			The Zeckendorf representation of 7 = 5 + 2, so a(7) = 2.
		

References

• D. E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.1.3, p. 82, solution to Problem 179. - From N. J. A. Sloane, Aug 03 2012

Links

• Steve Witham, Table of n, a(n) for n = 1..9999
• Alex Bogomolny, Theory of Take-Away Games
• Sylvain Rocher, Elodie Privat, Laurent Orban, Alexandre Mothe and Laurent Thouy, La stratégie des allumettes
• A. J. Schwenk, Take-Away Games, The Fibonacci Quarterly, v 8, no 3 (1970), 225-234.
• Eric Weisstein's World of Mathematics, Wythoff Array
• Wikipedia, Zeckendorf's theorem

Crossrefs

Cf. A000045, A035614, A107017, A014417, A006519.

Cf. A087172.

Programs

Haskell

a139764 = head . a035517_row  -- Reinhard Zumkeller, Mar 10 2013

Maple

A000045 := proc(n) combinat[fibonacci](n) ; end:
A087172 := proc(n)
local a,i ;
a := 0 ;
for i from 0 do
if A000045(i) <= n then
a := A000045(i) ;
else
RETURN(a) ;
fi ;
od:
end:
A139764 := proc(n)
local nResid,prevF ;
nResid := n ;
while true do
prevF := A087172(nResid) ;
if prevF = nResid then
RETURN(prevF) ;
else
nResid := nResid-prevF ;
fi ;
od:
end:
seq(A139764(n),n=1..120) ;
# R. J. Mathar, May 22 2008

Mathematica

f[n_] := (k = 1; ff = {}; While[(fi = Fibonacci[k]) <= n, AppendTo[ff, fi]; k++]; Drop[ff, 1]); a[n_] := First[ If[n == 0, 0, r = n; s = {}; fr = f[n]; While[r > 0, lf = Last[fr]; If[lf <= r, r = r - lf; PrependTo[s, lf]]; fr = Drop[fr, -1]]; s]]; Table[a[n], {n, 1, 89}] (* Jean-François Alcover, Nov 02 2011 *)

PARI

a(n)=my(f);forstep(k=log(n*sqrt(5))\log(1.61803)+2, 2, -1, f=fibonacci(k);if(f<=n,n-=f;if(!n,return(f));k--)) \\ Charles R Greathouse IV, Nov 02 2011

Formula

a(n) = n if n is a Fibonacci number, else a( n - (largest Fibonacci number < n) ).

a(n) = the value of the (exactly one) digit that turns on between the Fibonacci-base representations of n-1 and n. E.g., from 6 (1001) to 7 (1010), the two's digit turns on.

a(n) = top element of the column of the Wythoff array that contains n.

a(n) = A000045(A035614(n-1) + 2). [Offsets made precise by Peter Munn, Apr 13 2021]

a(n) = A035517(n,0). - Reinhard Zumkeller, Mar 10 2013

Extensions

More terms from T. D. Noe and R. J. Mathar, May 22 2008