login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A214973 Number of terms in greedy representation of n using Fibonacci and Lucas numbers. 4
1, 1, 1, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 2, 2, 2, 2, 1, 2, 2, 1, 2, 2, 2, 2, 2, 3, 2, 1, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 3, 2, 2, 3, 3, 2, 3, 1, 2, 2, 2, 2, 2, 3, 2, 1, 2, 2, 2, 2, 2, 3, 2, 2, 3, 3, 2, 3, 2, 3, 3, 3, 3, 2, 3, 3, 1, 2, 2, 2, 2, 2, 3, 2, 2, 3, 3, 2, 3, 1, 2, 2, 2, 2, 2, 3, 2, 2, 3, 3 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,6

COMMENTS

Consider the sequence b = A116470 consisting of all the Fibonacci numbers and Lucas numbers.  For n>=0, let k(1) be the greatest k in the basis b = {b(k)} such that b(k) <= n, let k(2) be the greatest k in b such that k <= n-b(k(1)), and so on, resulting in the greedy b-representation (to be abbreviated as "rep") of n.  For comparison with the rep using A000045 as basis (called Zeckendorf, or Fibonacci, rep) and also with the rep using A000032 as basis (called the Lucas rep), it is natural to ask this:  what terms in b can possibly follow a given term b(k)?  The answer follows.

If b(k) < 21 = b(11), the terms that can follow b(k) are easily found and not recorded here.  Otherwise, if k is odd, then b(k) can be followed by b(k-i) for some i>=5; if k is even, then b(k) can be followed by b(k-i) for some i>=8.  In Zeckendorf and Lucas reps, the "lag" is k-i for i>=2.

LINKS

Clark Kimberling, Table of n, a(n) for n = 1..10000

EXAMPLE

Let F, L, U denote the Fibonacci (aka Zeckendorf), Lucas, and greedy F-union-L representations.  Then 45 = 34+8+3 (F) = 29+11+4+1 (L) = 34+11 (U), which shows that a(45) = 2 and that the U representation of 45 requires fewer terms than the others; 45 is the least number having this property.

MATHEMATICA

s = Reverse[Union[Flatten[Table[{Fibonacci[n + 1], LucasL[n - 1]}, {n, 1, 22}]]]]; Map[Length[Select[Reap[FoldList[(Sow[Quotient[#1, #2]]; Mod[#1, #2]) &, #, s]]

[[2, 1]], # > 0 &]] &, Range[120]]

(* Peter J. C. Moses, Oct 18 2012 *)

CROSSREFS

Cf. A000032, A000045, A007895, A116470.

Sequence in context: A093914 A007061 A001817 * A091954 A325167 A213408

Adjacent sequences:  A214970 A214971 A214972 * A214974 A214975 A214976

KEYWORD

nonn

AUTHOR

Clark Kimberling, Oct 20 2012

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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 11 01:51 EDT 2020. Contains 335600 sequences. (Running on oeis4.)