cp's OEIS Frontend

A139764 Smallest term in Zeckendorf representation of n.

%I A139764 #50 Feb 16 2025 08:33:08
%S A139764 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 A139764 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 A139764 1,13,1,2,3,1,5,1,2,21,1,2,3,1,5,1,2,8,1,2,3,1,89
%N A139764 Smallest term in Zeckendorf representation of n.
%C A139764 Also called a "Fibonacci fractal".
%C A139764 Appears to be the same as the "ruler of Fibonaccis" mentioned by Knuth. - _N. J. A. Sloane_, Aug 03 2012
%C A139764 a(n) is also the number of matches to take away to win in a certain match game (see Rocher et al.).
%C A139764 The frequencies of occurrences of the values in this sequence and A035614 are related by the golden ratio.
%D A139764 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 A139764 Steve Witham, <a href="/A139764/b139764.txt">Table of n, a(n) for n = 1..9999</a>
%H A139764 Alex Bogomolny, <a href="http://www.cut-the-knot.org/Curriculum/Games/TakeAway.shtml#theory">Theory of Take-Away Games</a>
%H A139764 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 A139764 A. J. Schwenk, <a href="https://web.archive.org/web/2024*/https://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 A139764 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/WythoffArray.html">Wythoff Array</a>
%H A139764 Wikipedia, <a href="http://en.wikipedia.org/wiki/Zeckendorf&#39;s_theorem">Zeckendorf's theorem</a>
%F A139764 a(n) = n if n is a Fibonacci number, else a( n - (largest Fibonacci number < n) ).
%F A139764 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 A139764 a(n) = top element of the column of the Wythoff array that contains n.
%F A139764 a(n) = A000045(A035614(n-1) + 2). [Offsets made precise by _Peter Munn_, Apr 13 2021]
%F A139764 a(n) = A035517(n,0). - _Reinhard Zumkeller_, Mar 10 2013
%e A139764 The Zeckendorf representation of 7 = 5 + 2, so a(7) = 2.
%p A139764 A000045 := proc(n) combinat[fibonacci](n) ; end:
%p A139764 A087172 := proc(n)
%p A139764 local a,i ;
%p A139764 a := 0 ;
%p A139764 for i from 0 do
%p A139764 if A000045(i) <= n then
%p A139764 a := A000045(i) ;
%p A139764 else
%p A139764 RETURN(a) ;
%p A139764 fi ;
%p A139764 od:
%p A139764 end:
%p A139764 A139764 := proc(n)
%p A139764 local nResid,prevF ;
%p A139764 nResid := n ;
%p A139764 while true do
%p A139764 prevF := A087172(nResid) ;
%p A139764 if prevF = nResid then
%p A139764 RETURN(prevF) ;
%p A139764 else
%p A139764 nResid := nResid-prevF ;
%p A139764 fi ;
%p A139764 od:
%p A139764 end:
%p A139764 seq(A139764(n),n=1..120) ;
%p A139764 # _R. J. Mathar_, May 22 2008
%t A139764 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 A139764 (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 A139764 (Haskell)
%o A139764 a139764 = head . a035517_row  -- _Reinhard Zumkeller_, Mar 10 2013
%Y A139764 Cf. A000045, A035614, A107017, A014417, A006519.
%Y A139764 Cf. A087172.
%K A139764 nonn,nice
%O A139764 1,2
%A A139764 Steve Witham (sw(AT)tiac.net), May 15 2008
%E A139764 More terms from _T. D. Noe_ and _R. J. Mathar_, May 22 2008