A031439 a(0) = 1, a(n) is the greatest prime factor of a(n-1)^2+1 for n > 0.

1, 2, 5, 13, 17, 29, 421, 401, 53, 281, 3037, 70949, 1713329, 1467748131121, 37142837524296348426149, 101591133424866642486477019709, 1650979973845742266714536305651329, 78343914631785958284737, 4029445531112797145738746391569, 350080544438648120162733678636001, 26208090024628793745288451837610346882122253572537, 4717815978577117335515270825550279551117660519482308365269206484133871485221

Offset

0,2

Comments

Does this sequence grow indefinitely, or does it cycle? - Franklin T. Adams-Watters, Oct 02 2006

All a(n) except a(0) = 1 belong to A014442(n) = {2, 5, 5, 17, 13, 37, 5, 13, 41, 101, ...} Largest prime factor of n^2 + 1. All a(n) except a(0) = 1 belong to A002313(n) = {2, 5, 13, 17, 29, 37, 41, 53, 61, 73, 89, 97, 101, ...} Primes congruent to 1 or 2 modulo 4; or, primes of form x^2+y^2; or, -1 is a square mod p. All a(n) except a(0) = 1 and a(1) = 2 are the Pythagorean primes A002144(n) = {5, 13, 17, 29, 37, 41, 53, 61, 73, 89, 97, 101, ...} Primes of form 4n+1. - Alexander Adamchuk, Nov 05 2006

Essentially the same as A072268; A072268(n) = A031439(n-1)^2 + 1. - Charles R Greathouse IV, May 08 2009

Links

Dennis Langdeau, Table of n, a(n) for n = 0..24

Dario A. Alpern, Factorization: Elliptic Curve Method

Jason Papadopoulos, Integer Factorization Source Code.

Example

a(16)=A006530(a(15)^2+1)=
A006530(101591133424866642486477019709^2+1)=
A006530(10320758390549056348725939119133160378521185060950774444682)=
A006530(2*29*23201*4645528280970018601*1650979973845742266714536305651329)=
1650979973845742266714536305651329, factorization of A006530(a(15)^2+1) by Dario A. Alpern's program (see link).

Mathematica

gpf[n_] := FactorInteger[n][[-1, 1]]; a[0] = 1; a[n_] := a[n] = gpf[a[n - 1]^2 + 1]; Table[an = a[n]; Print[an]; an, {n, 0, 21}] (* Jean-François Alcover, Nov 04 2011 *)
NestList[FactorInteger[#^2+1][[-1, 1]]&, 1, 21] (* Harvey P. Dale, Jul 04 2013 *)

Prog

(PARI) gpf(n)=local(pf); pf=factor(n); pf[matsize(pf)[1], 1] vector(20, i, r=if(i==1, 1, gpf(r^2+1)))

Crossrefs

Cf. A056650, A003095.

Cf. A002144 - Pythagorean primes: primes of form 4n+1; A002313 - Primes congruent to 1 or 2 modulo 4; A014442 - Largest prime factor of n^2 + 1.

Cf. also A072268, A056650, A003095, A125256.

Sequence in context: A068486 A099332 A279687 * A074856 A087952 A124255

Adjacent sequences: A031436 A031437 A031438 * A031440 A031441 A031442

Keyword

nonn,nice

Author

Yasutoshi Kohmoto

Extensions

One more term from Vladeta Jovovic, Nov 26 2001

a(16) from Reinhard Zumkeller, Aug 07 2004

a(17)-a(21) from Richard FitzHugh (fitzhughrichard(AT)hotmail.com), Aug 12 2004

Status

approved