|
%I #108 Mar 11 2023 08:17:15
%S 2,5,5,17,13,37,5,13,41,101,61,29,17,197,113,257,29,13,181,401,17,97,
%T 53,577,313,677,73,157,421,53,37,41,109,89,613,1297,137,17,761,1601,
%U 29,353,37,149,1013,73,17,461,1201,61,1301,541,281,2917,89,3137,13,673
%N Largest prime factor of n^2 + 1.
%C All a(n) except for a(1) = 2 are the Pythagorean primes, i.e., primes of form 4k+1. Conjecture: every Pythagorean prime appears in a(n) at least once.
%C Problem 11831 [Ozols 2015] is to prove that lim inf a(n)/n is zero. - _Michael Somos_, May 11 2015
%C From _Michael Kaltman_, Jun 10 2015: (Start)
%C For all numbers k in A256011, a(k) < k.
%C 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).
%C (End)
%C 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
%C 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
%C 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
%C 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
%C 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
%C Note that a(n) is the largest prime p such that n^(p+1) == -1 (mod p). - _Thomas Ordowski_, Nov 08 2019
%D 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.
%D H. Rademacher, Lectures on Elementary Number Theory, pp. 33-38.
%H T. D. Noe, <a href="/A014442/b014442.txt">Table of n, a(n) for n = 1..10000</a>
%H S. Chowla, <a href="http://doi.org/10.1112/jlms/s1-10.1.117">The greatest prime factor of x^2 + 1</a>, J. London Math. Soc. 10 (1935), 117--120.
%H J. M. Deshouillers and H. Iwaniec, <a href="http://dx.doi.org/10.5802/aif.891">On the greatest prime factor of n^2+1</a>, Annales de l'institut Fourier, 32 no. 4 (1982), p. 1-11.
%H Christopher Hooley, <a href="https://projecteuclid.org/euclid.acta/1485889502">On the greatest prime factor of a quadratic polynomial</a>, Acta Mathematica 117 (1967), pp. 281-299.
%H Jori Merikoski, <a href="https://arxiv.org/abs/1908.08816">Largest prime factor of n^2+1</a>, arXiv:1908.08816 [math.NT], 2019.
%H R. Ozols, <a href="http://www.jstor.org/stable/10.4169/amer.math.monthly.122.04.390">Problem 11831</a>, The American Mathematical Monthly, Vol. 122, No. 4 (April 2015), page 390
%H A. Schinzel, <a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa13/aa13113.pdf">On two theorems of Gelfond and some of their applications</a>, Acta Arith. 13 (1967), 177--236.
%H Carl Størmer, <a href="http://www.archive.org/stream/skrifterudgivnea1897chri#page/n79/mode/2up">Quelques théorèmes sur l'équation de Pell x^2 - Dy^2 = +-1 et leurs applications</a> (in French), Skrifter Videnskabs-selskabet (Christiania), Mat.-Naturv. Kl. I (2), 48 pp.
%F a(n) = A006530(1+n^2). - _R. J. Mathar_, Jan 28 2017
%p seq(max(numtheory:-factorset(n^2+1)),n=1..100) ; # _Robert Israel_, Jun 11 2015
%t 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 *)
%t a[ n_] := If[ n < 1, 0, FactorInteger[n n + 1][[All, 1]] // Last]; (* _Michael Somos_, May 11 2015 *)
%t Table[FactorInteger[n^2 + 1][[-1, 1]], {n, 80}] (* _Vincenzo Librandi_, Jun 17 2015 *)
%o (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
%o (PARI) {a(n) = if( n<1, 0, Vecrev(factor(n*n + 1)[,1])[1])}; /* _Michael Somos_, May 11 2015 */
%o (Magma) [Maximum(PrimeDivisors(n^2+1)): n in [1..60]]; // _Vincenzo Librandi_, Jun 17 2015
%o (GAP) List([1..60],n->Reversed(Factors(n^2+1))[1]); # _Muniru A Asiru_, Oct 27 2018
%Y Includes primes from A002496.
%Y Cf. A002144 (Pythagorean primes: primes of form 4n+1).
%Y Cf. A256011.
%Y Cf. A076605 (largest prime factor of n^2 - 1).
%K nonn,easy
%O 1,1
%A Glen Burch (gburch(AT)erols.com)
|
