A085722 -id:A085722 - cp's OEIS frontend

A089120 Smallest prime factor of n^2 + 1.

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

A144255 Semiprimes of the form k^2+1.

Original entry on oeis.org

10, 26, 65, 82, 122, 145, 226, 362, 485, 626, 785, 842, 901, 1157, 1226, 1522, 1765, 1937, 2026, 2117, 2305, 2402, 2501, 2602, 2705, 3365, 3482, 3601, 3722, 3845, 4097, 4226, 4762, 5042, 5777, 6085, 6242, 6401, 7226, 7397, 7745, 8465, 9026, 9217, 10001, 10202

Offset: 1

T. D. Noe, Sep 16 2008

Iwaniec proves that there are an infinite number of semiprimes or primes of the form n^2+1. Because n^2+1 is not a square for n>0, all such semiprimes have two distinct prime factors.

Moreover, this implies that one prime factor p of n^2+1 is strictly smaller than n, and therefore also divisor of (the usually much smaller) m^2+1, where m = n % p (binary "mod" operation). - M. F. Hasler, Mar 11 2012

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Henryk Iwaniec, Almost-primes represented by quadratic polynomials, Inventiones Mathematicae 47 (2) (1978), pp. 171-188.

Cf. A001358, A085722, A069987, A193432.

Subsequence of A134406.

IsSemiprime:= func; [s: n in [1..100] | IsSemiprime(s) where s is n^2 + 1]; // Vincenzo Librandi, Sep 22 2012

Select[Table[n^2  + 1, {n, 100}], PrimeOmega[#] == 2&] (* Vincenzo Librandi, Sep 22 2012 *)

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

from sympy import primeomega
from itertools import count, takewhile
def aupto(limit):
    form = takewhile(lambda x: x <= limit, (k**2+1 for k in count(1)))
    return [number for number in form if primeomega(number)==2]
print(aupto(10202)) # Michael S. Branicky, Oct 26 2021

a(n) = A085722(n)^2 + 1.

Equals { n^2+1 | A193432(n)=2 }. - M. F. Hasler, Mar 11 2012

A105041 Positive integers k such that k^7 + 1 is semiprime.

Original entry on oeis.org

2, 10, 16, 18, 46, 52, 66, 72, 78, 106, 136, 148, 226, 228, 240, 262, 282, 330, 442, 508, 616, 630, 732, 750, 756, 768, 810, 828, 910, 936, 982, 1032, 1060, 1128, 1216, 1302, 1366, 1558, 1626, 1696, 1698, 1758, 1800, 1810, 1830, 1932, 1996, 2002, 2026, 2080

Offset: 1

Jonathan Vos Post, Apr 03 2005

We have the polynomial factorization n^7+1 = (n+1) * (n^6 - n^5 + n^4 - n^3 + n^2 - n + 1). Hence after the initial n=1 prime, the binomial can at best be semiprime and that only when both (n+1) and (n^6 - n^5 + n^4 - n^3 + n^2 - n + 1) are primes.

			n n^7+1 = (n+1) * (n^6 - n^5 + n^4 - n^3 + n^2 - n + 1).
2 129 = 3 * 43
10 10000001 = 11 * 909091
16 268435457 = 17 * 15790321
18 612220033 = 19 * 32222107
46 435817657217 = 47 * 9272716111

Robert Price, Table of n, a(n) for n = 1..1414

Cf. A001358, A085722, A096173, A186669, A104238, A103854, A105041, A105066, A105078, A105122, A105142, A105237, A104335, A104479, A104494, A104657, A105282.

IsSemiprime:=func< n | &+[ k[2]: k in Factorization(n) ] eq 2 >; [n: n in [1..2100] | IsSemiprime(n^7+1)]; // Vincenzo Librandi, Mar 12 2015

Select[Range[0,200000], PrimeQ[# + 1] && PrimeQ[(#^7 + 1)/(# + 1)] &] (* Robert Price, Mar 11 2015 *)
Select[Range[2500], Plus@@Last/@FactorInteger[#^7 + 1]==2 &] (* Vincenzo Librandi, Mar 12 2015 *)
Select[Range[2100],PrimeOmega[#^7+1]==2&] (* Harvey P. Dale, Jun 18 2019 *)

is(n)=isprime(n+1) && isprime((n^7+1)/(n+1)) \\ Charles R Greathouse IV, Aug 31 2021

a(n)^7 + 1 is semiprime. a(n)+1 is prime and a(n)^6 - a(n)^5 + a(n)^4 - a(n)^3 + a(n)^2 - a(n) + 1 is prime.

More terms from R. J. Mathar, Dec 14 2009

A103854 Positive integers n such that n^6 + 1 is semiprime.

Original entry on oeis.org

2, 4, 10, 36, 56, 94, 126, 224, 260, 270, 300, 350, 686, 716, 780, 1036, 1070, 1080, 1156, 1174, 1210, 1394, 1416, 1434, 1440, 1460, 1524, 1550, 1576, 1616, 1654, 1660, 1700, 1756, 1860, 1980, 2054, 2084, 2096, 2116, 2224, 2454, 2600, 2664, 2770, 2864

Offset: 1

Jonathan Vos Post, Mar 31 2005

n^6+1 can only be prime when n = 1, n^6+1 = 2. This is because the sum of cubes formula gives the polynomial factorization n^6+1 = (n^2+1) * (n^4 - n^2 + 1). Hence n^6+1 can only be semiprime when both (n^2+1) and (n^4 - n^2 + 1) are primes.

			n n^6+1 = (n^2+1) * (n^4 - n^2 + 1)
2 65 = 5 * 13
4 4097 = 17 * 241
10 1000001 = 101 * 9901
36 2176782337 = 1297 * 1678321
56 30840979457 = 3137 * 9831361
94 689869781057 = 8837 * 78066061
126 4001504141377 = 15877 * 252031501
224 126324651851777 = 50177 * 2517580801

Robert Price, Table of n, a(n) for n = 1..1134

Subsequence of A005574.

Cf. A001358, A001538, A085722, A096173, A186669, A104238, A103854, A105041, A105066, A105078, A105122, A105142, A105237, A104335, A104479, A104494, A104657, A105282.

semiprimeQ[n_] := Plus @@ Last /@ FactorInteger[n] == 2; Select[ 2Range@1526, semiprimeQ[ #^6 + 1] &] (* Robert G. Wilson v, May 26 2006 *)
Select[Range[200000], PrimeQ[#^2 + 1] && PrimeQ[(#^6 + 1)/(#^2 + 1)] &] (* Robert Price, Mar 11 2015 *)

is(n)=my(s=n^2); isprime(s+1) && isprime(s^2-s+1) \\ Charles R Greathouse IV, Aug 31 2021

a(n)^6 + 1 is semiprime. (a(n)^2+1) is prime and (a(n)^4 - a(n)^2 + 1) is prime.

More terms from Robert G. Wilson v, May 26 2006

A105122 Positive integers n such that n^11 + 1 is semiprime.

Original entry on oeis.org

2, 6, 12, 232, 262, 280, 330, 430, 508, 772, 786, 852, 1012, 1522, 1566, 1626, 1810, 2346, 2556, 2676, 3658, 3888, 3910, 4018, 4048, 4258, 4830, 5188, 5322, 5478, 5848, 6090, 6366, 6568, 7018, 7458, 7602, 7606, 7822, 8178, 8928, 9420, 9618, 9676, 10398

Offset: 1

Jonathan Vos Post, Apr 08 2005

Since n^11 + 1 = (n+1) * (n^10 - n^9 + n^8 - n^7 + n^6 - n^5 + n^4 - n^3 + n^2 - n + 1), n^11 + 1 can be prime only if both (n+1) and (n^10 - n^9 + n^8 - n^7 + n^6 - n^5 + n^4 - n^3 + n^2 - n + 1) are prime.

			2^11+1 = 2049 = 3 * 683,
6^11+1 = 362797057 = 7 * 51828151,
1012^11+1 = 1140212079231804336089593374834689 = 1013 * 1125579545144920371263172137053.

Robert Price, Table of n, a(n) for n = 1..4303

Cf. A001358 (semiprimes), A085722, A096173, A186669, A104238, A103854, A105041, A105066, A105078, A105122, A105142, A105237, A104335, A104479, A104494, A104657, A105282.

Select[ Range[10721], PrimeQ[ # + 1] && PrimeQ[(#^11 + 1)/(# + 1)] &] (* Robert G. Wilson v, Apr 09 2005 *)

More terms from Robert G. Wilson v, Apr 09 2005

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.

A104335 Positive integers n such that n^14 + 1 is semiprime (A001358).

Original entry on oeis.org

4, 74, 94, 116, 270, 464, 556, 654, 1140, 1156, 1246, 1306, 1736, 2464, 2470, 2604, 2804, 2836, 2900, 3054, 3890, 4006, 4056, 4330, 4736, 4780, 5016, 5294, 5340, 5486, 5700, 5834, 6434, 7114, 7304, 8626, 8880, 9164, 9546, 9744, 9980, 10086, 10166

Offset: 1

Jonathan Vos Post, Apr 17 2005

x^14+1 has factors (1 + x^2) (1 - x^2 + x^4 - x^6 + x^8 - x^10 + x^12).

			4^14 + 1 = 268435457 = 17 * 15790321,
74^14 + 1 = 147653612273582215982104577 = 5477 * 26958848324553992328301,
1140^14 + 1 = 6261349103849104148619671961600000000000001 = 1299601 * 4817901112610027345792802530622860401.

Robert Price, Table of n, a(n) for n = 1..1114

Cf. A001358, A085722, A096173, A186669, A104238, A103854, A105041, A105066, A105078, A105122, A105142, A105237, A104335, A104479, A104494, A104657, A105282.

Select[ Range[2, 10422, 2], PrimeQ[ #^2 + 1] && PrimeQ[ #^12 - #^10 + #^8 - #^6 + #^4 - #^2 + 1] &] (*Robert G. Wilson v, Apr 18 2005 *)
Select[Range[2,10200,2],PrimeOmega[#^14+1]==2&] (* Harvey P. Dale, Oct 16 2011 *)

More terms from Robert G. Wilson v, Apr 18 2005

A104479 Positive integers n such that n^16 + 1 is semiprime (A001358).

Original entry on oeis.org

3, 4, 9, 12, 14, 16, 18, 20, 26, 29, 40, 41, 48, 58, 70, 73, 81, 87, 92, 96, 104, 111, 113, 114, 118, 122, 130, 140, 142, 144, 146, 150, 157, 162, 164, 167, 168, 172, 173, 184, 187, 192, 194, 195, 199, 200, 202, 208, 220, 230, 232, 244, 253, 256, 266, 278, 292, 295, 298

Offset: 1

Jonathan Vos Post, Apr 18 2005

n^16 + 1 is an irreducible polynomial over Z and thus can be either prime (A006313) or semiprime.

			3^16 + 1 = 43046722 = 2 * 21523361,
4^16 + 1 = 4294967297 = 641 * 6 700417,
9^16 + 1 = 1853020188851842 = 2 * 926510094425921,
12^16 + 1 = 184884258895036417 = 153953 * 1200913648289,
200^16 + 1 = 6553600000000000000000000000000000001 =
162123499503471553 * 40423504427621041217.

Robert Price, Table of n, a(n) for n = 1..102

Cf. A006313, A001358, A085722, A096173, A186669, A104238, A103854, A105041, A105066, A105078, A105122, A105142, A105237, A104335, A104479, A104494, A104657, A105282.

IsSemiprime:=func< n | &+[ k[2]: k in Factorization(n) ] eq 2 >; [n: n in [2..300]|IsSemiprime(n^16+1)] // Vincenzo Librandi, Dec 21 2010

Select[Range[300],PrimeOmega[#^16+1]==2&] (* Harvey P. Dale, Aug 21 2011 *)
Select[Range[1000], 2 == Total[Transpose[FactorInteger[#^16 + 1]][[2]]] &] (* Robert Price, Mar 11 2015 *)

a(n)^16 + 1 is semiprime (A001358).

More terms from Vincenzo Librandi, Dec 21 2010

Corrected (adding 202, 208, and 220) by Harvey P. Dale, Aug 21 2011

A105078 Positive integers n such that n^10 + 1 is semiprime.

Original entry on oeis.org

4, 16, 26, 54, 110, 120, 126, 260, 314, 420, 444, 470, 570, 646, 714, 890, 946, 1010, 1294, 1306, 1394, 1640, 1674, 1794, 1920, 1964, 2116, 2174, 2360, 2430, 2624, 2666, 2884, 2924, 3094, 3106, 3174, 3220, 3504, 3686, 3826, 3884, 3924, 4046, 4540, 4700

Offset: 1

Jonathan Vos Post, Apr 06 2005

We have the polynomial factorization: n^10+1 = (n^2+1) * (n^8 - n^6 + n^4 - n^2 + 1) Hence after the initial n=1 prime the binomial can only be semiprime if n^2 + 1 is prime and n^8 - n^6 + n^4 - n^2 + 1 is prime.

			4^10+1 = 1048577 = 17 * 61681,
16^10+1 = 1099511627777 = 257 * 4278255361,
1010^10+1 = 1104622125411204510010000000001 = 1020101 * 1082855644108970101989901.

Robert Price, Table of n, a(n) for n = 1..1105

Cf. A001358, A085722, A096173, A186669, A104238, A103854, A105041, A105066, A105078, A105122, A105142, A105237, A104335, A104479, A104494, A104657, A105282.

Select[ Range[5000], PrimeQ[ #^2 + 1] && PrimeQ[(#^10 + 1)/(#^2 + 1)] &] (* Robert G. Wilson v, Apr 08 2005 *)
Select[Range[4700], PrimeOmega[#^10+1]==2&] (* Harvey P. Dale, Jan 13 2013 *)

More terms from Robert G. Wilson v, Apr 08 2005

A105142 Positive integers n such that n^12 + 1 is semiprime.

Original entry on oeis.org

2, 6, 34, 46, 142, 174, 204, 238, 312, 466, 550, 616, 690, 730, 1136, 1280, 1302, 1330, 1486, 1586, 1610, 1638, 1644, 1652, 1688, 1706, 1772, 1934, 1952, 1972, 2040, 2102, 2108, 2142, 2192, 2238, 2250, 2376, 2400, 2554, 2612, 2646, 3006, 3094, 3550, 3642

Offset: 1

Jonathan Vos Post, Apr 09 2005

Since n^12 + 1 = (n^4+1) * (n^8 - n^4 + 1), n^12 + 1 can be semiprime only if both n^4 + 1 and n^8 - n^4 + 1 are prime.

			2^12+1 = 4097 = 17 * 241,
6^12+1 = 2176782337 = 1297 * 1678321,
34^12+1 = 2386420683693101057 = 1336337 * 1785792568561,
1136^12+1 = 4618915067251126036363854530631172097 = 1665379926017 * 2773490297975392253706241.

Robert Price, Table of n, a(n) for n = 1..1515

Cf. A001358 (semiprimes), A085722, A096173, A186669, A104238, A103854, A105041, A105066, A105078, A105122, A105142, A105237, A104335, A104479, A104494, A104657, A105282.

Select[ Range@3691, PrimeQ[ #^4 + 1] && PrimeQ[(#^12 + 1)/(#^4 + 1)] &] (* Robert G. Wilson v *)
Select[Range[4000],PrimeOmega[#^12+1]==2&] (* Harvey P. Dale, Jan 24 2013 *)

a(16)-a(46) from Robert G. Wilson v, Feb 10 2006

cp's OEIS Frontend

A089120 Smallest prime factor of n^2 + 1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

Formula

A144255 Semiprimes of the form k^2+1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Python

Formula

A105041 Positive integers k such that k^7 + 1 is semiprime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

A103854 Positive integers n such that n^6 + 1 is semiprime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A105122 Positive integers n such that n^11 + 1 is semiprime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

A104335 Positive integers n such that n^14 + 1 is semiprime (A001358).

Views

Author

Keywords