login
This site is supported by donations to The OEIS Foundation.

 

Logo

Please make a donation to keep the OEIS running. We are now in our 55th year. In the past year we added 12000 new sequences and reached 8000 citations (which often say "discovered thanks to the OEIS"). We need to raise money to hire someone to manage submissions, which would reduce the load on our editors and speed up editing.
Other ways to donate

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..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^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

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

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 5 13:26 EST 2019. Contains 329751 sequences. (Running on oeis4.)