20080227, 00:42  #1 
(loop (#_fork))
Feb 2006
Cambridge, England
5·31·41 Posts 
A missing identity
I feel that L2185A, an Aurifeullian factor of lucas(2185) which equals 5*fib(437)^2  5*fib(437) + 1, ought to be an SNFSnumber.
But I can't work out how to attack it. There are any number of identities writing one Fibonacci number in terms of others, but they're almost all homogeneous in terms of some pair of Fibonacci numbers  for example, fib(437) = A^3 + 3AB^2 + B^3 where A=fib(145), B=fib(146)  and so no use if I want to expand an expression containing both fib(437) and fib(437)^2. fib(3n) = 5*fib(n)^3 + 3*fib(n), but 437 isn't a multiple of 3, and a bit of lattice reduction fails to find any expressions for fib(437) in terms of powers of fib(145) or fib(146) alone with reasonable coefficients. 
20080301, 10:22  #2 
Feb 2005
2^{2}·3^{2}·7 Posts 
why not simply to represent the number N=fib(437) as whatever best polynomial of degree 2 or 3 (not even referring to fibonaccity of N) and substitute it into 5*N^2  5*N + 1 to get its representation as a polynomial of degree 4 or 6 ?
If that does not work, please explain why and, in particular, what are the "reasonable coefficients". Last fiddled with by maxal on 20080301 at 10:25 
20080303, 01:46  #3  
Feb 2005
2^{2}·3^{2}·7 Posts 
Quote:
5 * F(437)^2 = L(874) + 2 = (3*L(876) + L(870))/8 + 2 = (L(146)^6  6*L(146)^4 + 9*L(146)^2  2)*3/8 + (L(145)^6 + 6*L(145)^4 + 9*L(145)^2 + 2)*1/8 + 2 5 * F(437) = (3*L(3*146)  L(3*145)) / 2 = (L(146)^3  3*L(146))*3/2  (L(145)^3 + 3*L(145))/2 Therefore: 5*F(437)^2  5*F(437) + 1 = [ (3*L(146)^6  18*L(146)^4  12*L(146)^3 + 27*L(146)^2 + 36*L(146)) + (L(145)^6 + 6*L(145)^4 + 4*L(145) + 9*L(145)^2 + 12*L(145)) + 20 ] / 8 Does that work for you? 

20080303, 14:11  #4 
(loop (#_fork))
Feb 2006
Cambridge, England
5·31·41 Posts 
The problem is that SNFS requires a homogeneous polynomial as input; so you can use a decomposition of Fib(x) as a normal polynomial in Fib(y) and use A=Fib(y), B=1, or you can decompose it as a homogeneous polynomial in A=Fib(y) and B=Fib(z).
What you can't use is a nonhomogeneous polynomial in Fib(y) and Fib(z). 'reasonable coefficients' means two or three digits; constructions giving polynomials with coefficients some power of the input have most of the drawbacks of GNFS. 
20080304, 05:04  #5 
Feb 2005
FC_{16} Posts 
OK.
Here is a homogeneous polynomial of the degree 4 of x=L(219) and y=L(218): 5*F(437)^2  5*F(437) + 1 = ( y^4  3*x*y^3 + 9*x^2*y^2  7*x^3*y + 11*x^4 ) / 25 Similarly, this is a homogeneous polynomial of the degree 8 of x=L(110) and y=L(109): 5*F(437)^2  5*F(437) + 1 = ( 11*y^8  76*x*y^7 + 222*x^2*y^6  308*x^3*y^5 + 170*x^4*y^4 + 38*x^5*y^3 + 37*x^6*y^2 + 6*x^7*y + x^8 ) / 625 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Bicurvious Identity  jcrombie  Miscellaneous Math  51  20130909 18:51 
Cpu Identity mismatch  only_human  Software  2  20120511 13:43 
I had my identity stolen by '24'  ewmayer  Lounge  12  20100204 21:26 
Useful Identity?  grandpascorpion  Math  2  20091110 20:44 
Number and identity of nth roots of 1 mod p  SPWorley  Math  6  20090828 18:02 