

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^n1 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.
a(n) is the smallest number x > 2 such that A001222(x^n1) = A000005(n).  Thomas Ordowski, Jan 31 2018
All terms are in A008864. If n is even, a(n) is in A014574.  Robert Israel, Jan 31 2018


LINKS

Don Reble, Table of n, a(n) for n = 1..47
Don Reble, Table of n, a(n) for n = 1..99 (with question marks at the unknown entries)


EXAMPLE

a(16)=4 because 4^161 = 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:
map(f, [$1..29]); # Robert Israel, Jan 31 2018


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

Cf. A000005, A001222, A008864, A014574, A070737.
Sequence in context: A006984 A087275 A265305 * A025267 A223169 A201420
Adjacent sequences: A072939 A072940 A072941 * A072943 A072944 A072945


KEYWORD

nonn


AUTHOR

Phil Carmody, Aug 12 2002


EXTENSIONS

Corrected and extended by Don Reble, Feb 03 2014
Edited by N. J. A. Sloane, Mar 01 2014 at the suggestion of Phil Carmody and Don Reble


STATUS

approved



