login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A139764 Smallest term in Zeckendorf representation of n. 6
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

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.

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

Author?, Title? (see p. 24) [Broken link]

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 Math, Wythoff Array

Wikipedia, Zeckendorf's theorem

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) = Fibonacci(A035614(n) + 1).

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

EXAMPLE

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

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

PROG

(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

(Haskell)

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

CROSSREFS

Cf. A035614, A107017, A014417, A006519.

Cf. A087172.

Sequence in context: A187680 A140706 A200068 * A227643 A249386 A089026

Adjacent sequences:  A139761 A139762 A139763 * A139765 A139766 A139767

KEYWORD

nonn,nice

AUTHOR

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

EXTENSIONS

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 24 07:50 EST 2018. Contains 299599 sequences. (Running on oeis4.)