|
|
A072942
|
|
a(n) is the least x such that the cyclotomic polynomial values Phi(d,x) are prime for all d dividing n.
|
|
1
|
|
|
3, 4, 3, 4, 12, 6, 3, 4, 3, 12, 20, 24687390, 3, 72, 62, 4, 20, 1102903830, 12, 58051620, 3, 1793172, 468, 1035844571580, 62, 882, 398, 75274140, 6, 81206805256038, 14, 1288005000, 78428, 93888, 37664, 24380304369772260, 432, 3300, 21962
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,1
|
|
COMMENTS
|
An equivalent formulation is that a(n) is smallest number x such that x^n-1 factors only into its algebraic factors.
Many more terms are known, in particular terms at prime indices. Massively composite n are the hardest to find - term 256 alone took a month to find. Contact the author for more terms beyond the gaps.
2 never appears in the sequence because Phi(1,2) = 1, which is irreducible but not prime.
|
|
LINKS
|
|
|
EXAMPLE
|
a(16)=4 because 4^16-1 = 3*5*17*257*65537, which are the 5 algebraic factors.
|
|
MAPLE
|
f:= proc(n) local p, C, x, d;
C:= [seq(numtheory:-cyclotomic(d, x), d = numtheory:-divisors(n) minus {1})];
p:= 1;
do
p:= nextprime(p);
if andmap(isprime, subs(x=p+1, C)) then return p+1 fi
od:
end proc:
|
|
MATHEMATICA
|
Table[With[{d = Divisors@ n}, SelectFirst[Range[10^3], AllTrue[Cyclotomic[d, #], PrimeQ] &]], {n, 11}] (* Michael De Vlieger, Jan 31 2018 *)
|
|
PROG
|
(PARI) for(d=1, 17, ds=divisors(d); print("Searching for d|"d":"ds); forprime(p=2, 499999, okc=1; for(c=2, length(ds), if(!isprime(subst(polcyclo(ds[c]), x, p+1)), okc=0; break)); if(okc, for(c=1, length(ds), print("Phi("ds[c]", "p+1")="subst(polcyclo(ds[c]), x, p+1))); break)))
(PARI) isok(n, x) = {fordiv(n, d, if (! isprime(polcyclo(d, x)), return(0)); ); return(1); }
a(n) = {my(x=2); while (! isok(n, x), x++); x; } \\ Michel Marcus, Jan 31 2018
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
Corrected and extended by Don Reble, Feb 03 2014
|
|
STATUS
|
approved
|
|
|
|