login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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.
a(n) is the smallest number x > 2 such that A001222(x^n-1) = 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..99 (with question marks at the unknown entries)
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:
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
Sequence in context: A361458 A087275 A265305 * A025267 A223169 A201420
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 18 22:56 EDT 2024. Contains 370952 sequences. (Running on oeis4.)