Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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 at 13:24

2 Answers 2

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

share|improve this answer
1  
$\phi^n - \psi^n$, not $\phi^n + \psi^n$. –  Daniel Fischer May 8 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 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.

share|improve this answer
    
Your approximations aren't all that good for the first few Fibonaccis, so your plan may not work if one of the two Fibonacci factors is small. –  Gerry Myerson May 8 at 13:20
    
Hm, OK, then you should try the first few manually. –  john_leo May 8 at 13:23

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.