A164511 Least prime p such that p^2+1 is the product of n distinct primes.

2, 3, 13, 47, 463, 2917, 30103, 241727, 3202337, 26066087, 455081827, 7349346113, 122872146223, 2523038248697, 28435279521433, 119919330795347

Offset: 1

Author

T. D. Noe, Aug 14 2009

Keywords

• hard
• nonn
• more

Comments

For n>1, there appear to be an infinite number of primes q for which q^2+1 is the product of n distinct primes (and thus has 2^n divisors). This sequence gives the smallest such prime for each n. See A048161 for primes q such that q^2+1 has two prime factors. Note that all prime factors of p^2+1 must be 2 or primes of the form 4k+1.

Examples

			1+2^2 = 5
1+3^2 = 2*5
1+13^2 = 2*5*17
1+47^2 = 2*5*13*17
1+463^2 = 2*5*13*17*97
1+2917^2 = 2*5*13*29*37*61
1+30103^2 = 2*5*13*17*41*73*137
1+241727^2 = 2*5*13*17*29*37*41*601
1+3202337^2 = 2*5*13*17*29*41*73*193*277
1+26066087^2 = 2*5*13*17*29*37*41*89*233*337
1+455081827^2 = 2*5*13*17*37*53*61*73*97*317*349
		

Crossrefs

Cf. A180278.

Programs

Mathematica

nn=8; t=Table[0,{nn}]; p=1; While[Times@@t==0, While[p=NextPrime[p]; {q,e}=Transpose[FactorInteger[p^2+1]]; !(Union[e]=={1} && Length[e]<=nn && t[[Length[e]]]==0)]; t[[Length[e]]]=p]; t

PARI

generate(A, B, n) = A=max(A, vecprod(primes(n))); (f(m, p, j) = my(list=List()); my(s=sqrtnint(B\m, j)); if(j==1, forprime(q=max(p, ceil(A/m)), s, if(q%4 == 3, next); my(v=m*q); if(issquare(v-1) && isprime(sqrtint(v-1)), listput(list, sqrtint(v-1)))), forprime(q=p, s, if(q%4 == 3, next); list=concat(list, f(m*q, q+1, j-1)))); list); vecsort(Vec(f(1, 2, n)));
a(n) = my(x=vecprod(primes(n)), y=2*x); while(1, my(v=generate(x, y, n)); if(#v >= 1, return(v[1])); x=y+1; y=2*x); \\ Daniel Suteu, Feb 20 2023

Formula

a(n) >= A180278(n). - Daniel Suteu, Feb 20 2023

Extensions

a(12)-a(13) from Donovan Johnson, Oct 09 2009

a(14)-a(16) from Daniel Suteu, Feb 20 2023