 mersenneforum.org A missing identity
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read 2008-02-27, 00:42 #1 fivemack (loop (#_fork))   Feb 2006 Cambridge, England 18EF16 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 SNFS-number. 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.   2008-03-01, 10:22 #2 maxal   Feb 2005 22×32×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 2008-03-01 at 10:25   2008-03-03, 01:46   #3
maxal

Feb 2005

22·32·7 Posts Quote:
 Originally Posted by fivemack any expressions for fib(437) in terms of powers of fib(145) or fib(146) alone with reasonable coefficients.
There is an expression in terms of powers of L(145) and L(146) (Lucas numbers):

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?   2008-03-03, 14:11 #4 fivemack (loop (#_fork))   Feb 2006 Cambridge, England 143578 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 non-homogeneous 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.   2008-03-04, 05:04 #5 maxal   Feb 2005 FC16 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 Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post jcrombie Miscellaneous Math 51 2013-09-09 18:51 only_human Software 2 2012-05-11 13:43 ewmayer Lounge 12 2010-02-04 21:26 grandpascorpion Math 2 2009-11-10 20:44 SPWorley Math 6 2009-08-28 18:02

All times are UTC. The time now is 16:20.

Fri Apr 16 16:20:35 UTC 2021 up 8 days, 11:01, 0 users, load averages: 2.57, 2.56, 2.30

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.