A014442 -id:A014442 - cp's OEIS frontend

A089121 Duplicate of A014442.

2, 5, 5, 17, 13, 37, 5, 13, 41, 101, 61, 29, 17, 197, 113, 257, 29, 13, 181, 401, 17, 97

Offset: 1

dead

A085722 Numbers k such that k^2 + 1 is a semiprime.

3, 5, 8, 9, 11, 12, 15, 19, 22, 25, 28, 29, 30, 34, 35, 39, 42, 44, 45, 46, 48, 49, 50, 51, 52, 58, 59, 60, 61, 62, 64, 65, 69, 71, 76, 78, 79, 80, 85, 86, 88, 92, 95, 96, 100, 101, 102, 104, 106, 108, 114, 121, 131, 136, 139, 140, 141, 144, 145, 152, 154, 158, 159, 164

Offset: 1

Jason Earls, Jul 20 2003

Corresponding semiprimes k^2+1 are in A144255.

Solutions to the equation: A000005(1+k^2) = 4. - Enrique Pérez Herrero, May 03 2012

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

Cf. A014442, A089120, A144255, A193432.

lst={}; Do[If[Plus@@Last/@FactorInteger[n^2+1]==2, AppendTo[lst,n]], {n,0,200}]; lst (* Vladimir Joseph Stephan Orlovsky, Mar 24 2009 *)
Select[Range[200],PrimeOmega[#^2+1]==2&] (* Harvey P. Dale, Feb 28 2013 *)

select(vector(50,n,n),n->bigomega(n^2+1)==2)
\\ Zak Seidov, Feb 25 2011

A085722 = A193432^-1({2}). - M. F. Hasler, Mar 11 2012

A076605 Largest prime divisor of n^2 - 1.

Original entry on oeis.org

3, 2, 5, 3, 7, 3, 7, 5, 11, 5, 13, 7, 13, 7, 17, 3, 19, 5, 19, 11, 23, 11, 23, 13, 5, 13, 29, 7, 31, 5, 31, 17, 11, 17, 37, 19, 37, 19, 41, 7, 43, 11, 43, 23, 47, 23, 47, 5, 17, 13, 53, 13, 53, 7, 19, 29, 59, 29, 61, 31, 61, 31, 13, 11, 67, 17, 67, 17, 71, 7

Offset: 2

Jon Perry, Oct 21 2002

nonn

Also the largest prime that divides either n-1 or n+1.

Størmer shows that a(n) tends to infinity with n. Schinzel shows that lim inf a(n)/log log n >= 2 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

			n=11: the largest prime factor of 10 and 12 is 5, therefore a(11) = 5.

K. Mahler, "Uber den grossten Primteiler spezieller Polynome zweiten Grades", Arch. Math. Naturvid. B.41, 1935, pp. 3 - 26.

T. D. Noe, Table of n, a(n) for n = 2..10000
D. H. Lehmer, On a problem of Størmer, Ill. J. Math., 8 (1964), 57-79.
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 udgivne af Videnskabsselskabet i Christiania: Mathematisk-naturvidenskabelig Klasse, 2 (1897), 48 pp.

Cf. A006530, A037464, A074399 (bisections).
Cf. A175607.
Cf. A014442 (largest prime divisor of n^2 + 1). - Tomohiro Yamada, Apr 15 2017

Table[ Last[ Table[ # [[1]]] & /@ FactorInteger[n^2 - 1]], {n, 2, 80}]

for (n=3,100, print1(","max(factor(n-1)[,1][length(factor(n-1)[,1])],factor(n+1)[,1][length(factor(n+1)[,1])])))

A089120 Smallest prime factor of n^2 + 1.

Original entry on oeis.org

2, 5, 2, 17, 2, 37, 2, 5, 2, 101, 2, 5, 2, 197, 2, 257, 2, 5, 2, 401, 2, 5, 2, 577, 2, 677, 2, 5, 2, 17, 2, 5, 2, 13, 2, 1297, 2, 5, 2, 1601, 2, 5, 2, 13, 2, 29, 2, 5, 2, 41, 2, 5, 2, 2917, 2, 3137, 2, 5, 2, 13, 2, 5, 2, 17, 2, 4357, 2, 5, 2, 13, 2, 5, 2, 5477, 2, 53, 2, 5, 2, 37, 2, 5, 2

Offset: 1

Cino Hilliard, Dec 05 2003

This includes A002496, primes that are of the form n^2+1.

Note that a(n) is the smallest prime p such that n^(p+1) == -1 (mod p). - Thomas Ordowski, Nov 08 2019

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

Michael De Vlieger, Table of n, a(n) for n = 1..10000

Cf. A002496, A014442, A085722, A144255, A193432.

[Min(PrimeDivisors(n^2+1)):n in [1..100]]; // Marius A. Burtea, Nov 13 2019

Array[FactorInteger[#^2 + 1][[1, 1]] &, {83}] (* Michael De Vlieger, Sep 08 2015 *)

smallasqp1(m) = { for(a=1,m, y=a^2 + 1; f = factor(y); v = component(f,1); v1 = v[length(v)]; print1(v[1]",") ) }

A089120(n)=factor(n^2+1)[1,1]  \\ M. F. Hasler, Mar 11 2012

a(2k+1)=2; a(10k +/- 2)=5, else a(26k +/- 8)=13, else a(34k +/- 4)=17, else a(58k +/- 12)=29, else a(74k +/- 6)=37,... - M. F. Hasler, Mar 11 2012

A089120(n) = 2 if n is odd, else A089120(n) = min { A002144(k) | n = +/- A209874(k) (mod 2*A002144(k)) }.

A081256 Greatest prime factor of n^3 + 1.

Original entry on oeis.org

2, 3, 7, 13, 7, 31, 43, 19, 73, 13, 37, 19, 157, 61, 211, 241, 13, 307, 7, 127, 421, 463, 13, 79, 601, 31, 37, 757, 271, 67, 19, 331, 151, 1123, 397, 97, 43, 67, 1483, 223, 547, 1723, 139, 631, 283, 109, 103, 61, 181, 43, 2551, 379, 919, 409, 2971, 79, 103, 3307, 163

Offset: 1

Jan Fricke, Mar 14 2003

Record values appear to match the terms of A002383 for n>1. - Bill McEachen, Oct 18 2023

R. J. Mathar and T. D. Noe, Table of n, a(n) for n = 1..10000 (first 5000 terms from R. J. Mathar)
J. Buchmann, K. Győry, M. Mignotte, and N. Tzanakis, Lower bounds for P(x^3+k), an elementary approach, Publ. Math. Debrecen, Vol. 38, No. 1-2 (1991), pp. 145-163.

Cf. A081257, A081258, A096173, A096174.

Cf. A006530, A001093, A002383, A014442, A096172.

A081256 := proc(n)
    A006530(n^3+1) ;
end proc:
seq(A081256(n),n=1..20) ; # R. J. Mathar, Feb 13 2014

Table[Max[Transpose[FactorInteger[n^3 + 1]][[1]]], {n, 25}]

a(n)=my(f=factor(n^3+1)); f[#f~,1] \\ Charles R Greathouse IV, Mar 08 2017

A081256(n)=vecmax(factor(n^3+1)[,1]) \\ It seems slightly slower to get the last element using ...[-1..-1][1]. - M. F. Hasler, Jun 15 2018

a(n) = A006530(A001093(n)). - M. F. Hasler, Jun 13 2018

a(n) >= 31 for n >= 70 (Buchmann et al., 1991). - Amiram Eldar, Oct 25 2024

More terms from Harvey P. Dale, Mar 22 2003

More terms from Hugo Pfoertner, Jun 20 2004

A209874 Least m > 0 such that the prime p=A002313(n+1) divides m^2+1.

Original entry on oeis.org

1, 2, 8, 4, 12, 6, 32, 30, 50, 46, 34, 22, 10, 76, 98, 100, 44, 28, 80, 162, 112, 14, 122, 144, 64, 16, 82, 60, 228, 138, 288, 114, 148, 136, 42, 104, 274, 334, 20, 266, 392, 254, 382, 348, 48, 208, 286, 52, 118, 86, 24, 516, 476, 578, 194, 154, 504, 106, 58, 26, 566, 96, 380, 670, 722, 62, 456, 582, 318, 526, 246, 520, 650, 726, 494, 324

Offset: 0

M. F. Hasler, Mar 11 2012

nonn

This yields the prime factors of numbers of the form N^2+1, cf. formula in A089120: For n=0,1,2,... check whether N = +/- a(n) [mod 2*A002313(n+1)], if so, then A002313(n+1) is a prime factor of N^2+1.
Obviously, p then divides (2kp +/- a(n))^2+1 for all k >=0 ; in particular it will be the least prime factor of such numbers if there is no earlier match.
Alternatively one could deal separately with the case of odd N, for which p=2 divides N^2+1, and even N, for which only Pythagorean primes A002144(n)=A002313(n+1) can be prime factors of N^2+1.

Cf. A002496, A014442, A085722, A144255, A089120, A193432.

Cf. A002314, A177979.

A209874(n)=if( n, 2*lift(sqrt(Mod(-1, A002144[n])/4)), 1)

/* for illustrative purpose: a(n) is the smaller of the 2 possible remainders mod 2*p of numbers N such that N^2+1 has p as smallest prime factor */ forprime( p=1,199, p>2 & p%4 != 1 & next; my(c=[]); for(i=1,9e9, factor(i^2+1)[1,1]==p |next; c=vecsort(concat(c,i%(2*p)),,8); #c==1 || print1(","c[1]) || break))

For n>0, A209874(n) = 2*sqrt(-1/4 mod A002144(n)), where sqrt(a mod p) stands for the positive x < p/2 such that x^2=a in Z/pZ.

A209874(n) = A209877(n)*2 for n>0.

A096172 Largest prime factor of n^4 + 1.

Original entry on oeis.org

2, 17, 41, 257, 313, 1297, 1201, 241, 193, 137, 7321, 233, 14281, 937, 1489, 65537, 41761, 929, 3833, 160001, 97241, 3209, 139921, 331777, 11489, 26881, 6481, 614657, 353641, 3361, 1129, 61681, 6113, 1336337, 750313, 98801, 10529, 50857, 1156721

Offset: 1

Hugo Pfoertner, Jun 19 2004

nonn

Mabkhout shows that a(n) >= 137 for n > 3. - Charles R Greathouse IV, Apr 07 2014

			a(1)=2 because 1^4 + 1 = 2;
a(2)=17: 2^4 + 1 = 17;
a(8)=241: 8^4 + 1 = 4097 = 17*241.

Mustapha Mabkhout, Minoration de P(x^4+1), Rendiconti del Seminario della Facoltà di Scienze dell'Università di Cagliari 63:2 (1993), pp. 135-148.

Vincenzo Librandi and T. D. Noe, Table of n, a(n) for n = 1..10000 (first 1000 terms from Vincenzo Librandi)
Florian Luca, Primitive divisors of Lucas sequences and prime factors of x^2 + 1 and x^4 + 1, Acta Academiae Paedagogicae Agriensis, Sectio Mathematicae 31 (2004), pp. 19-24.
Marina Mureddu, A lower bound for P(x^4+1), Annales de la Faculté des sciences de Toulouse: Mathématiques, Serie 5, Vol. 8, No. 2 (1986-1987), pp. 109-119.

Cf. A000068, A002523, A014442, A037896, A006530, A069170, A096169, A096171.

FactorInteger[#^4+1][[-1,1]]&/@Range[40] (* Harvey P. Dale, Apr 30 2012 *)

a(n)=my(f=factor(n^4+1)[,1]); f[#f] \\ Charles R Greathouse IV, Apr 07 2014

a(n) = A006530(1+n^4) = A014442(n^2). - R. J. Mathar, Jan 28 2017
From Amiram Eldar, Oct 28 2024: (Start)
a(n) > 113 for n > 3 (Mureddu, 1986-1987).
a(n) >= 233 for n >= 11 (Luca, 2004). (End)

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

Original entry on oeis.org

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

Offset: 0

Yasutoshi Kohmoto

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

			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).

Dennis Langdeau, Table of n, a(n) for n = 0..24
Dario A. Alpern, Factorization: Elliptic Curve Method
Jason Papadopoulos, Integer Factorization Source Code.

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.

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 *)

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

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

A256011 Integers n with the property that the largest prime factor of n^2 + 1 is less than n.

Original entry on oeis.org

7, 18, 21, 38, 41, 43, 47, 57, 68, 70, 72, 73, 83, 99, 111, 117, 119, 123, 128, 132, 133, 142, 157, 172, 173, 174, 182, 185, 191, 192, 193, 200, 211, 212, 216, 233, 237, 239, 242, 251, 253, 255, 265, 268, 273, 278, 293, 294, 302, 305, 307, 313, 319, 322, 327

Offset: 1

Michael Kaltman, May 31 2015

nonn

Every Pythagorean prime, p, can be written as the sum of two positive integers, a and b, such that ab is congruent to 1 (mod p). Further: no number is the addend of two different primes, and the numbers that are NEVER addends are precisely the numbers in this list.
In particular: 5 = 2+3 and 2*3 = 6 == 1 (mod 5), 13 = 5+8 and 5*8 = 40 == 1 (mod 13), 17 = 4+13 and 4*13 = 52 == 1 (mod 17), 29 = 12+17 and 12*17 = 204 == 1 (mod 29), and so on.
Every integer greater than 1 is in exactly one of A002314, A152676, and the present sequence. - Michael Kaltman, May 11 2019

			7^2 + 1 = 50 = 2 * 5^2;
18^2 + 1 = 325 = 5^2 * 13;
21^2 + 1 = 442 = 2 * 13 * 17.

Giovanni Resta, Table of n, a(n) for n = 1..10000

Cf. A002144 (Pythagorean primes), A014442, A002314, A152676.

[k:k in [1..330]| Max(PrimeDivisors(k^2+1)) lt k]; // Marius A. Burtea, Jul 27 2019

select(n -> max(numtheory:-factorset(n^2+1))Robert Israel, Jun 09 2015

Select[Range[10^4], FactorInteger [#^2 + 1][[-1, 1]] < # &] (* Giovanni Resta, Jun 09 2015 *)

for(n=1,10^3,N=n^2+1;if(factor(N)[,1][omega(N)] < n,print1(n,", "))) \\ Derek Orr, Jun 08 2015

is(n)=my(f=factor(n^2+1)[,1]); f[#f]Charles R Greathouse IV, Jun 09 2015

A240548 Greatest prime factor of n^5 + 1.

Original entry on oeis.org

2, 11, 61, 41, 521, 101, 191, 331, 1181, 9091, 13421, 19141, 2411, 101, 1531, 61681, 101, 9041, 2251, 152381, 185641, 224071, 211, 5791, 9161, 1021, 271, 53951, 401, 71261, 21821, 4051, 1151041, 259631, 132631, 6781, 1824841, 2031671, 41011, 20641, 4111, 23201

Offset: 1

T. D. Noe, Apr 07 2014

nonn

			a(2) = 11 because 2^5 + 1 = 33 = 3 * 11.
a(3) = 61 because 3^5 + 1 = 244 = 2^2 * 61.
a(4) = 41 because 4^5 + 1 = 1025 = 5^2 * 41.
a(2272) = 2273 because 2272^5 + 1 = 11^2 * 311 * 491 * 1171 * 1231 * 2273.

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

Cf. A002561, A014442, A081256, A096172, A240549-A240553.

Table[FactorInteger[n^5 + 1][[-1, 1]], {n, 100}]

cp's OEIS Frontend

A089121 Duplicate of A014442.

Views

Author

Keywords

A085722 Numbers k such that k^2 + 1 is a semiprime.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A076605 Largest prime divisor of n^2 - 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

A089120 Smallest prime factor of n^2 + 1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

Formula

A081256 Greatest prime factor of n^3 + 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A209874 Least m > 0 such that the prime p=A002313(n+1) divides m^2+1.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

PARI

Formula

A096172 Largest prime factor of n^4 + 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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