A139764 - OEIS

%I #47 May 01 2021 17:52:00

%S 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,

%T 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,

%U 1,13,1,2,3,1,5,1,2,21,1,2,3,1,5,1,2,8,1,2,3,1,89

%N Smallest term in Zeckendorf representation of n.

%C Also called a "Fibonacci fractal".

%C Appears to be the same as the "ruler of Fibonaccis" mentioned by Knuth. - _N. J. A. Sloane_, Aug 03 2012

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

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

%D 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

%H Steve Witham, <a href="/A139764/b139764.txt">Table of n, a(n) for n = 1..9999</a>

%H Alex Bogomolny, <a href="http://www.cut-the-knot.org/Curriculum/Games/TakeAway.shtml#theory">Theory of Take-Away Games</a>

%H Sylvain Rocher, Elodie Privat, Laurent Orban, Alexandre Mothe and Laurent Thouy, <a href="http://mathematiques.ac-bordeaux.fr/elv/clubs/mej/mej2005/allumettes.pdf">La stratégie des allumettes</a>

%H A. J. Schwenk, <a href="http://www.fq.math.ca/Scanned/8-3/schwenk-a.pdf">Take-Away Games</a>, The Fibonacci Quarterly, v 8, no 3 (1970), 225-234.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/WythoffArray.html">Wythoff Array</a>

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Zeckendorf&#39;s_theorem">Zeckendorf's theorem</a>

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

%F 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.

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

%F a(n) = A000045(A035614(n-1) + 2). [Offsets made precise by _Peter Munn_, Apr 13 2021]

%F a(n) = A035517(n,0). - _Reinhard Zumkeller_, Mar 10 2013

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

%p A000045 := proc(n) combinat[fibonacci](n) ; end:

%p A087172 := proc(n)

%p local a,i ;

%p a := 0 ;

%p for i from 0 do

%p if A000045(i) <= n then

%p a := A000045(i) ;

%p else

%p RETURN(a) ;

%p fi ;

%p od:

%p end:

%p A139764 := proc(n)

%p local nResid,prevF ;

%p nResid := n ;

%p while true do

%p prevF := A087172(nResid) ;

%p if prevF = nResid then

%p RETURN(prevF) ;

%p else

%p nResid := nResid-prevF ;

%p fi ;

%p od:

%p end:

%p seq(A139764(n),n=1..120) ;

%p # _R. J. Mathar_, May 22 2008

%t 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 *)

%o (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

%o (Haskell)

%o a139764 = head . a035517_row  -- _Reinhard Zumkeller_, Mar 10 2013

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

%Y Cf. A087172.

%K nonn,nice

%O 1,2

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

%E More terms from _T. D. Noe_ and _R. J. Mathar_, May 22 2008