|
|
A164511
|
|
Least prime p such that p^2+1 is the product of n distinct primes.
|
|
1
|
|
|
2, 3, 13, 47, 463, 2917, 30103, 241727, 3202337, 26066087, 455081827, 7349346113, 122872146223, 2523038248697, 28435279521433, 119919330795347
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,1
|
|
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.
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
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
|
|
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
|
|
PROG
|
(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
|
|
CROSSREFS
|
|
|
KEYWORD
|
hard,nonn,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|