login
Positive integers n such that Fibonacci(2*n) is the sum of two squares.
6

%I #63 Jun 27 2022 15:59:21

%S 1,3,6,7,13,19,31,37,43,49,61,67,73,79,91,111,127,163,169,183,199,223,

%T 307,313,349,361,397,433,511,523,541,613,619,709,823,907,1087,1123,

%U 1129,1147,1213,1279

%N Positive integers n such that Fibonacci(2*n) is the sum of two squares.

%C This sequence excludes Fibonacci numbers with odd indices, all of which are sums of two squares.

%C Fibonacci numbers with even indices factor as F_2n = F_n L_n, L_n being n-th Lucas number. Thus F_2n factors further as F_2n = F_m L_m L_2m L_4m...L_n, with m odd. Since F_m is a sum of two squares and the pairs of Lucas numbers all have GCD dividing 2, the conclusion for F_2n depends on each Lucas number being a sum of two squares. Joint work with Kevin O'Bryant and Dennis Eichhorn.

%C To write Fibonacci(n) as a^2+b^2: find the a^2+b^2 representation for the individual prime factors, by using Cornacchia's algorithm, and then merge them by using the formulas (a^2+b^2)(c^2+d^2) = |ac+bd|^2 + |ad-bc|^2 = |ac-bd|^2 + |ad+bc|^2. - _V. Raman_, Aug 29 2012

%C All corresponding Fibonacci(2*n) values are the sum of two nonzero distinct squares except n = 1, 3, 6. - _Altug Alkan_, May 04 2016

%C 1501 <= a(43) <= 1651. 1651, 1849, 2449 are terms. - _Chai Wah Wu_, Jul 22 2020

%H Blair Kelly, <a href="http://mersennus.net/fibonacci">Fibonacci and Lucas factorizations</a>

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Cornacchia%27s_algorithm">Cornacchia's algorithm</a>

%e a(4) = 7 because the first four Fibonacci numbers with even indices that are the sum of two squares are F_2, F_6, F_12 and F_14, 14 being 2*a(4) and F_14 = 377 = 11^2+16^2.

%t Select[Range[100], Length[FindInstance[x^2 + y^2 == Fibonacci[2 #], {x, y}, Integers]] > 0 &] (* _T. D. Noe_, Aug 27 2012 *)

%o (PARI) for(i=2, 500, a=factorint(fibonacci(i))~; has=0; for(j=1, #a, if(a[1, j]%4==3&&a[2, j]%2==1, has=1; break)); if(has==0&&i%2==0, print((i/2)", "))) \\ _V. Raman_, Aug 27 2012

%o (Python)

%o from itertools import count, islice

%o from sympy import factorint, fibonacci

%o def A124132_gen(): # generator of terms

%o return filter(lambda n:all(p & 3 != 3 or e & 1 == 0 for p, e in factorint(fibonacci(2*n)).items()),count(1))

%o A124132_list = list(islice(A124132_gen(),10)) # _Chai Wah Wu_, Jun 27 2022

%Y Cf. A001906, A124130 (for Lucas numbers), A001481.

%K nonn,more

%O 1,2

%A Melvin J. Knight (melknightdr(AT)verizon.net), Nov 30 2006

%E a(22)-a(38) from _V. Raman_, Aug 27 2012

%E a(39)-a(42) from _Chai Wah Wu_, Jul 22 2020