# Check if the number is a result of multiplying two fibonacci numbers

Is there a way to check if a given number is a result of multiplication of two fibonacci numbers? Any theory/characteristics allowing to quickly decline some of these given numbers?

-
These numbers are tabulated at oeis.org/A049997 --- have a look at the links at that page, maybe something useful there. – Gerry Myerson May 8 '14 at 13:24

Fibonacci numbers can be written as $F_n=\frac1{\sqrt 5}(\phi^n+\psi^n)$ with $\phi=\frac{1+\sqrt 5}{2}$, $\psi=\frac{1-\sqrt 5}{2}$. Thus $$5F_nF_m=\phi^{n+m}+\phi^n\psi^m+\psi^n\phi^m+\psi^{m+n}$$ If $n>m$, this becomes (using $\phi\psi=-1$) $$5F_nF_m=\phi^{n+m}+\phi^{n-m}(-1)^m+\psi^{n-m}(-1)^m+\psi^{m+n}$$ So the idea is:
• Compute $k=\left\lfloor\frac12+\frac{\ln 5x}{\ln\phi}\right\rfloor$. This should be $n+m$.
• With $y=5x-\phi^k$ compute $d=\left\lfloor\frac12+\frac{\ln |y|}{\ln\phi}\right\rfloor$. If at all, we should have $n=\frac{k+d}{2}$, $m=\frac{k-d}2$ (especially, if $k+d$ is odd$, there is no solution) Since this approach relies on smallness of both$\psi^{n-m}$and$\psi^{m+n}$, one should check specifically if$x=F_k =F_kF_1$or$x=F_{k/2}^2=F_k\pm1$(may happen if$y$is small). -$\phi^n - \psi^n$, not$\phi^n + \psi^n$. – Daniel Fischer May 8 '14 at 13:25 i tried your solution but it just doesn't work, that's my code: PHI = (1+sqrt(5))/2; k = floor(0.5 + log(5*x)/log(PHI)); y = 5*x - pow(PHI,k); d = floor(0.5 + log(abs(y))/log(PHI)); kd= k+d; n = (k+d)/2; m = (k-d)/2; and k+d is often odd, and anwsers are wrong – bkrasinski May 9 '14 at 21:36 Let's assume that your$n$is the product of two large Fibonacci numbers,$f_1$and$f_2$, hence$ n = f_1 \cdot f_2$(you can use trial division for the first small numbers). Then we know that $$f_1 \approx \frac{1}{\sqrt 5} \phi^{p_1} \quad \text{and} \quad f_2 \approx \frac{1}{\sqrt 5} \phi^{p_2}$$ where$\phi $is the golden ratio. So we know that$\log_{\phi} 5n$must be very close to an integer. Note that this is only a necessary condition: Eg. if one of the numbers is very close to a Fibonacci number, then$\log_{\phi} 5n $will still be very close to an integer. But you will know a lot about the possible form of the Fibonacci-factorization: Namely$p_1 + p_2 \approx \log_{\phi} 5n\$. From there you can easily brute-force your search.