login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A014442 Largest prime factor of n^2 + 1. 39
2, 5, 5, 17, 13, 37, 5, 13, 41, 101, 61, 29, 17, 197, 113, 257, 29, 13, 181, 401, 17, 97, 53, 577, 313, 677, 73, 157, 421, 53, 37, 41, 109, 89, 613, 1297, 137, 17, 761, 1601, 29, 353, 37, 149, 1013, 73, 17, 461, 1201, 61, 1301, 541, 281, 2917, 89, 3137, 13, 673 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

All a(n) except a(1) = 2 are the Pythagorean primes, or primes of form 4n+1. Conjecture: every Pythagorean prime appears in a(n) at least once.

Problem 11831 [Ozols 2015] is to prove that lim inf a(n)/n is zero. - Michael Somos, May 11 2015

From Michael Kaltman, Jun 10 2015: (Start)

For all numbers k in A256011, a(k) < k.

Conjecture: every Pythagorean prime p appears exactly two times among the first p integers of the sequence. Further: if a(i) = a(j) = p and both i and j are less than p (and i is not equal to j), then i + j = p and ij == 1 mod p. [If a(k) = p as well, then k > p; in fact, k is in A256011.] Two examples: a(2) = a(3) = 5, with 2+3 = 5 and 2*3 = 6 == 1 mod 5; a(4) = a(13) = 17, with 4+13 = 17 and 4*13 = 52 == 1 mod 17.

(End)

The conjecture is true. If p is a Pythagorean prime, -1 is a quadratic residue mod p. Then -1 has exactly two square roots mod p, i.e., there are exactly two integers x,y with 1 <= x,y <= p-1 such that x^2 == y^2 == -1 mod p, i.e., p divides x^2+1 and y^2+1, and moreover y == -x mod p so x + y = p, and x y == -x^2 == 1 mod p. Any other prime factor q of x^2 + 1 must divide (x^2+1)/p, and since x^2+1 < p^2 we have q < p, so a(x) = p and similarly a(y) = p. - Robert Israel, Jun 11 2015

Conjecture: if n is even and a(n)>n, then n+a(n) is in A256011. Examples: 2+a(2) = 2+5 = 7, 4+a(4) = 4+17 = 21, 6+a(6) = 6+37 = 43, and so on. Note that 18+a(18) is NOT in A256011, but 18 itself is. - Michael Kaltman, Jun 13 2015

This is also true. Suppose A = a(n) > n. n^2+1 is odd so A is an odd prime; n^2 + 1 = A B with B < A also odd. Then (A+n)^2 + 1 = A (A+2 n+B) and A+2 n+B is even. The largest prime factor of A+2 n+B is thus at most (A+2 n+B)/2 < A + n, while A < A + n as well. - Robert Israel, Jun 17 2015

Størmer shows that a(n) tends to infinity with n.  Chowla shows that a(n) >> log log n.  Schinzel shows that lim inf a(n)/log log n >= 4 and, using lower bounds for linear forms of logarithms, this inequality can be generalized for general quadratic polynomials, with 2 replaced by 4/7 for irreducible ones and 2/7 for reducible ones. - Tomohiro Yamada, Apr 15 2017

According to Hooley, an unpublished manuscript of Chebyshev contains the result that a(n)/n is unbounded which was first published and fully proved by Markov. - Charles R Greathouse IV, Oct 27 2018

REFERENCES

A. A. Markov, Über die Primteiler der Zahlen von der Form 1+4x^2, Bulletin de l'Académie impériale des sciences de St.-Pétersbourg 3 (1895), pp. 55-59.

H. Rademacher, Lectures on Elementary Number Theory, pp. 33-38.

LINKS

T. D. Noe, Table of n, a(n) for n = 1..10000

S. Chowla, The greatest prime factor of x^2 + 1, J. London Math. Soc. 10 (1935), 117--120.

J. M. Deshouillers, H. Iwaniec, On the greatest prime factor of n^2+1, Annales de l'institut Fourier, 32 no. 4 (1982), p. 1-11.

Christopher Hooley, On the greatest prime factor of a quadratic polynomial, Acta Mathematica 117 (1967), pp. 281-299.

R. Ozols, Problem 11831, The American Mathematical Monthly, Vol. 122, No. 4 (April 2015), page 390

A. Schinzel, On two theorems of Gelfond and some of their applications, Acta Arith. 13 (1967), 177--236.

Carl Størmer, Quelques théorèmes sur l'équation de Pell x^2 - Dy^2 = +-1 et leurs applications (in French), Skrifter Videnskabs-selskabet (Christiania), Mat.-Naturv. Kl. I (2), 48 pp.

FORMULA

a(n) = A006530(1+n^2). - R. J. Mathar, Jan 28 2017

MAPLE

seq(max(numtheory:-factorset(n^2+1)), n=1..100) ; # Robert Israel, Jun 11 2015

MATHEMATICA

Table[FactorInteger[n^2+1, FactorComplete->True][[ -1, 1]], {n, 5!}] ..and/or.. Table[Last[Table[ #[[1]]]&/@FactorInteger[n^2+1]], {n, 5!}] ..and/or.. PrimeFactors[n_]:=Flatten[Table[ #[[1]], {1}]&/@FactorInteger[n]]; Table[PrimeFactors[n^2+1][[ -1]], {n, 5!}] (* Vladimir Joseph Stephan Orlovsky, Aug 12 2009 *)

a[ n_] := If[ n < 1, 0, FactorInteger[n n + 1][[All, 1]] // Last]; (* Michael Somos, May 11 2015 *)

Table[FactorInteger[n^2 + 1][[-1, 1]], {n, 80}] (* Vincenzo Librandi, Jun 17 2015 *)

PROG

(PARI) largeasqp1(m) = { for(a=1, m, y=a^2 + 1; f = factor(y); v = component(f, 1); v1 = v[length(v)]; print1(v1", ") ) } \\ Cino Hilliard, Jun 12 2004

(PARI) {a(n) = if( n<1, 0, Vecrev(factor(n*n + 1)[, 1])[1])}; /* Michael Somos, May 11 2015 */

(MAGMA) [Maximum(PrimeDivisors(n^2+1)): n in [1..60]]; // Vincenzo Librandi, Jun 17 2015

(GAP) List([1..60], n->Reversed(Factors(n^2+1))[1]); # Muniru A Asiru, Oct 27 2018

CROSSREFS

Includes primes from A002496.

Cf. A002144 (Pythagorean primes: primes of form 4n+1).

Cf. A256011.

Cf. A076605 (largest prime factor of n^2 + 1).

Sequence in context: A089793 A076570 A089121 * A281793 A259036 A081235

Adjacent sequences:  A014439 A014440 A014441 * A014443 A014444 A014445

KEYWORD

nonn,easy

AUTHOR

Glen Burch (gburch(AT)erols.com)

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 18 06:48 EDT 2019. Contains 322209 sequences. (Running on oeis4.)