Product of Fibonacci numbers

2012-07-18T13:36:30Z

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$.

Answer by Vladimir Dotsenko for Product of Fibonacci numbers

2012-07-18T23:52:17Z

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.

Answer by Douglas Zare for Product of Fibonacci numbers

2012-07-18T23:52:40Z

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.

Product of Fibonacci numbers - MathOverflow

Product of Fibonacci numbers

Answer by Vladimir Dotsenko for Product of Fibonacci numbers

Answer by Douglas Zare for Product of Fibonacci numbers