How do I apply the $\pm4$ part of the equation $5F_n^2\pm~4=L_n^2$ without knowing $n$?

Question

I'm trying to test a great many numbers $a^3+b^3$ to see if any of them are Fibonacci using the formula $$a^3+b^3=F_n \iff 5(a^3+b^3)^2\pm~4=L_n^2$$ I want to make my search more efficient by having some way of selecting one term, $+4$ or $-4$, that is the one more likely to produce a perfect square, and exclude the other one on the basis that it could never make a perfect square, instead of resorting to trial and error as I have been. What trick can I use to accomplish this?

Edit: I have since abandoned both the five-times-square test (initially in favor of the Mobius test, referred to in this question, which was faster) and also the looping through pairs of cubes (in favor of looping through Fibonacci indices instead). However, the answers below are helpful from a hypothetical-theoretical standpoint.

Answer 1

Suppose you want to check if $F$ is a fibonacci number.

One simple check you can do to cut down your perfect square check computations is to consider $r = F \mod 7$.

For some $r$ you can ignore one of $5F^2 \pm 4$ as that leaves a remainder which cannot lead to a perfect square (quadratic non-residue)

$r = 0$, you can ignore $5F^2 - 4$

$r = 2$, you can ignore $5F^2 + 4$

$r = 3$, you can ignore $5F^2 - 4$

etc.

For other $r$ ($r=1$ and $r=6$), you consider both $5F^2 \pm 4$

You might be able to choose numbers other than $7$ to cut it down even more, or have a nested if with a series of such remainders...

Answer 2

If you're trying to solve $F_n = a^3 + b^3$ (for instance in order to investigate MSE question 789588) then it's much more efficient to loop over $n$ than over $a$ and $b$. Thanks to the factorization $a^3 + b^3 = (a+b)(a^2-ab+b^2)$ it's enough to check for each solution of $xy=F_n$ whether $3(4x-y^2)$ is a square, since that's the criterion for $(x, y) = (a^2-ab+b^2, a+b)$ [the point is that $4x-y^2 = 3(a-b)^2$]. I did this for all $n \leq 300$ using this table of Fibonacci factorizations (discarding the 100 values of $n$ for which $F_n\bmod 9 \in \{3,4,5,6\}$, since such a number can never be the sum of two cubes). This took only ~30 seconds in gp, even though some candidates $F_n$ in this range have more than a million factors. Not surprisingly I found that in this range the only solutions of $F_n = a^3 + b^3$ (with the integers $a,b$ not necessarily positive) are the known $F_3 = 2 = 1^3 + 1^3$ and $F_6 = 8 = 2^3 + 0^3 = 0^3 + 2^3$.