A374209 Number of terms in Zeckendorf representation needed to write A113177(n), where A113177 is fully additive with a(p) = Fibonacci(p).

0, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 2, 1, 2, 2, 2, 1, 1, 1, 2, 2, 2, 1, 1, 2, 2, 2, 2, 1, 1, 1, 1, 2, 2, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 2, 1, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 1, 2, 1, 2, 3, 2, 2, 2, 1, 2, 2, 3, 1, 2, 1, 2, 3, 2, 2, 2, 1, 2, 1, 2, 1, 3, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 2, 1, 3, 3, 3, 1, 2, 1, 2, 3

Offset: 1

Author

Antti Karttunen, Jul 02 2024

Keywords

• nonn

Comments

Indices for the first occurrences of k=0..6 are: 1, 2, 9, 63, 693, 7623, 105105.

The claim a(n) <= bigomega(n) is true because A007895(n) is the minimum number of Fibonacci numbers which sum to n, regardless of adjacency or duplication. See Apr 17 2015 comments there.

Links

• Antti Karttunen, Table of n, a(n) for n = 1..129591
• Eric Weisstein's World of Mathematics, Fibonacci Number.
• Wikipedia, Zeckendorf's theorem.

Crossrefs

Cf. A000045, A001222, A007895, A030426, A113177.

Cf. also A328847, A328848.

Programs

PARI

A007895(n) = { my(s=0); while(n>0, s++; n -= fibonacci(1+A072649(n))); (s); }
A072649(n) = { my(m); if(n<1, 0, m=0; until(fibonacci(m)>n, m++); m-2); }; \\ From A072649
A113177(n) = if(n<=1, 0, my(f=factor(n)); sum(i=1, #f~, f[i, 2]*fibonacci(f[i,1])));
A374209(n) = if(isprime(n), 1, A007895(A113177(n)));

Formula

a(n) = A007895(A113177(n)).

a(p) = 1 for all primes p.

a(n) <= A001222(n), see comments.