Product of Fibonacci numbers - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T20:50:21Z http://mathoverflow.net/feeds/question/102540 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/102540/product-of-fibonacci-numbers Product of Fibonacci numbers Charles 2012-07-18T13:36:30Z 2012-07-18T23:52:40Z <p>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 <a href="https://oeis.org/A065108" rel="nofollow">A065108</a>.)</p> <p>What is known, asymptotically, about the growth of $f$?</p> <p>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$.</p> http://mathoverflow.net/questions/102540/product-of-fibonacci-numbers/102598#102598 Answer by Vladimir Dotsenko for Product of Fibonacci numbers Vladimir Dotsenko 2012-07-18T23:52:17Z 2012-07-18T23:52:17Z <p>A follow-up to the comment of Anonymous which addresses your question exactly: see slides 9-13 <a href="http://www.math.dartmouth.edu/~carlp/rademacherlecture3.pdf" rel="nofollow">here</a> 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.</p> http://mathoverflow.net/questions/102540/product-of-fibonacci-numbers/102599#102599 Answer by Douglas Zare for Product of Fibonacci numbers Douglas Zare 2012-07-18T23:52:40Z 2012-07-18T23:52:40Z <p>I think the following is related to Pietro Majer's comment:</p> <p><strong>Upper bound:</strong> 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$.</p> <p>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, </p> <p>$$f(x) \lt \frac{1+o(1)}{4\sqrt3} \exp (\pi \sqrt{\frac 23 \log_\phi x}).$$</p> <p>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})$.</p> <p><strong>Lower bound:</strong> $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$. </p> <p>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</p> <p>$$\exp(c \frac{\sqrt{\log_\phi x}}{\log_e\log_\phi x}) \lt f(x).$$</p> <p>See also <a href="http://mathoverflow.net/questions/69680/asymptotics-for-the-number-of-partitions-of-n-into-odd-prime-parts" rel="nofollow">this MO question</a> on the number of partitions into odd primes.</p>