cp's OEIS Frontend

A214973 Number of terms in greedy representation of n using Fibonacci and Lucas numbers.

%I A214973 #32 Jun 21 2024 14:32:12
%S A214973 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,
%T A214973 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,
%U A214973 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
%N A214973 Number of terms in greedy representation of n using Fibonacci and Lucas numbers.
%C A214973 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.
%C A214973 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.
%C A214973 Conjecture: a(A049651(n)) = n and this is the first instance of n in the sequence for all n > 0. In other words, apart from its initial term, A049651 is the RECORDS transform of this sequence. - _Charles R Greathouse IV_, Oct 14 2021
%H A214973 Clark Kimberling, <a href="/A214973/b214973.txt">Table of n, a(n) for n = 1..10000</a>
%H A214973 Jon Maiga, <a href="http://sequencedb.net/s/A214973">Computer-generated formulas for A214973</a>, Sequence Machine.
%F A214973 Conjecture: a(n) = A329320(A048679(n)) for n > 0 (noticed by Sequence Machine). - _Mikhail Kurkov_, Oct 13 2021
%e A214973 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.
%t A214973 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]]
%t A214973 [[2, 1]], # > 0 &]] &, Range[120]]
%t A214973 (* _Peter J. C. Moses_, Oct 18 2012 *)
%o A214973 (PARI) w(n)=if(n%2, fibonacci(n\2+3), fibonacci(n\2) + fibonacci(n\2+2));
%o A214973 k(n)=if(n<9, return(if(n==6,5,n))); for(i=8,n, if(w(i)>n, return(w(i-1))));
%o A214973 a(n)=my(s); while(n, n-=k(n); s++); s; \\ _Charles R Greathouse IV_, Oct 14 2021
%Y A214973 Cf. A000032, A000045, A007895, A116470.
%K A214973 nonn
%O A214973 1,6
%A A214973 _Clark Kimberling_, Oct 20 2012