Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Consider the counting function $$ f(x)=|\{n\le x:n\text{ is a product of Fibonacci numbers}\}| $$ so for example $f(4)=4=|\{1,2,3,4\}|$ since 1, 2, and 3 are Fibonacci numbers and $4=F_3\cdot F_3.$ (See A065108.)

What is known, asymptotically, about the growth of $f$?

It's clear that for any $k$, $f(x)\gg(\log x)^k$ (this can be made effective without too much work), and it doesn't seem likely that $f(x)\gg x^k$ for any $k>0$.

share|improve this question
    
The asymptotics $F_k\sim\phi^k/\sqrt{5}$ suggests an analogous additive counting function of the form: $$g(x):=|\{(k_1,k_2, \dots, k_r)\in\mathbb{N^r}: r > 0 , k_i\le k_{i+1}, \sum_{1\le j\le r} (k_j-c) \le \frac{\log n}{\log\phi}\}$$ –  Pietro Majer Jul 18 '12 at 17:20
2  
You might be interested in the work of Luca, Pomerance, and Wagner on the distribution of "Fibonacci integers". These are integers belonging to the group generated by the Fibonacci numbers (under multiplication). See math.dartmouth.edu/~carlp/fibint6.pdf –  Anonymous Jul 18 '12 at 18:14
    
@Anonymous: Interesting. That does give an upper bound on my sequence, though I think Fibonacci integers are rather more numerous than my sequence. –  Charles Jul 18 '12 at 19:02

2 Answers 2

up vote 9 down vote accepted

I think the following is related to Pietro Majer's comment:

Upper bound: The first $2$ Fibonacci numbers are $1$, so we can leave them out of products. The $n$th Fibonacci number is greater than $\phi^{n-2}$ for $\phi = \frac{1+\sqrt 5}{2}$. So, for any product of Fibonacci numbers less than $x$, there is a corresponding sum of exponents which is less than $\log_\phi x$. This means the number of integers up to $x$ which are products of Fibonacci numbers is at most the number of partitions of size up to $\log_\phi x$.

The number of partitions of $m$ are known to be asymptotically $\frac{1}{4\sqrt3 ~m} \exp (\pi \sqrt{\frac23m})$. the number of partitions is increasing, so the number of partitions of size up to $m$ is at most $m$ times this, or asymptotically $\frac{1}{4\sqrt3} \exp (\pi \sqrt{\frac23 m})$. So,

$$f(x) \lt \frac{1+o(1)}{4\sqrt3} \exp (\pi \sqrt{\frac 23 \log_\phi x}).$$

This is not sharp since some Fibonacci numbers are products of others: $8 =2^3, 144 = 2^4 3^2$. I don't know of any other such examples, so I think the growth rate is bounded above and below by functions of the form $\exp(c\sqrt{\log n})$.

Lower bound: $F_k \lt \phi^{k-1} \lt \phi^k$. We would like to construct distinct products of Fibonacci numbers out of some restricted partitions of $n \lt \log_\phi x$.

Note that $(F_m, F_n ) = F_{(m,n)}$. So, the Fibonacci numbers of prime index are relatively prime. We can't use the second Fibonacci number because that's $1$. However, partitions of $n \lt \log_\phi x$ into odd prime parts correspond to distinct products of Fibonacci numbers up to $x$. A crude lower bound is that there are at least $(1+o(1))\frac{\sqrt {2n}}{\log \sqrt{2n}}$ odd primes up to $\sqrt{2n}$ by the prime number theorem, and the subsets correspond to at least $\exp (c \frac {\sqrt{n}}{\log n})$ distinct partitions of numbers up to $n$ into odd primes hence to distinct products of Fibonacci numbers. So, for some $c \gt 0$, there is a lower bound for $x$ large enough for the formula to make sense of the form

$$\exp(c \frac{\sqrt{\log_\phi x}}{\log_e\log_\phi x}) \lt f(x).$$

See also this MO question on the number of partitions into odd primes.

share|improve this answer
1  
Our answers appeared simultaneously! :-) See my answer for a reference showing that the troubles of non-uniqueness you exhibited ($8=2^3$, $144=2^43^2$) are actually the only troubles that may occur, and we are reduced to counting partitions. –  Vladimir Dotsenko Jul 18 '12 at 23:58
    
Very nice. I had the same idea for the lower bound but didn't take it far enough so I got a much weaker bound, –  Charles Jul 19 '12 at 2:38
    
Powers of primes can also be distinguished. –  Douglas Zare Jul 29 '12 at 1:06

A follow-up to the comment of Anonymous which addresses your question exactly: see slides 9-13 here for an investigation of your question. Basically, it can be proved that the decomposition into a product of Fibonacci numbers is more or less unique (if you ignore the "special" Fibonacci numbers $f_1=1$, $f_2=1$, $f_6=8$, and $f_{12}=144$), and it all reduces to the asymptotics of the partition function in the spirit of Hardy--Ramanujan--Rademacher.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.