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