cp's OEIS Frontend

A072942 a(n) is the least x such that the cyclotomic polynomial values Phi(d,x) are prime for all d dividing n.

%I A072942 #47 Jul 12 2018 08:57:35
%S A072942 3,4,3,4,12,6,3,4,3,12,20,24687390,3,72,62,4,20,1102903830,12,
%T A072942 58051620,3,1793172,468,1035844571580,62,882,398,75274140,6,
%U A072942 81206805256038,14,1288005000,78428,93888,37664,24380304369772260,432,3300,21962
%N A072942 a(n) is the least x such that the cyclotomic polynomial values Phi(d,x) are prime for all d dividing n.
%C A072942 An equivalent formulation is that a(n) is smallest number x such that x^n-1 factors only into its algebraic factors.
%C A072942 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.
%C A072942 2 never appears in the sequence because Phi(1,2) = 1, which is irreducible but not prime.
%C A072942 a(n) is the smallest number x > 2 such that A001222(x^n-1) = A000005(n). - _Thomas Ordowski_, Jan 31 2018
%C A072942 All terms are in A008864. If n is even, a(n) is in A014574. - _Robert Israel_, Jan 31 2018
%H A072942 Don Reble, <a href="/A072942/b072942.txt">Table of n, a(n) for n = 1..47</a>
%H A072942 Don Reble, <a href="/A072942/a072942.txt">Table of n, a(n) for n = 1..99</a> (with question marks at the unknown entries)
%e A072942 a(16)=4 because 4^16-1 = 3*5*17*257*65537, which are the 5 algebraic factors.
%p A072942 f:= proc(n) local p, C, x, d;
%p A072942   C:= [seq(numtheory:-cyclotomic(d,x), d = numtheory:-divisors(n) minus {1})];
%p A072942   p:= 1;
%p A072942   do
%p A072942     p:= nextprime(p);
%p A072942     if andmap(isprime, subs(x=p+1, C)) then return p+1 fi
%p A072942   od:
%p A072942 end proc:
%p A072942 map(f, [$1..29]); # _Robert Israel_, Jan 31 2018
%t A072942 Table[With[{d = Divisors@ n}, SelectFirst[Range[10^3], AllTrue[Cyclotomic[d, #], PrimeQ] &]], {n, 11}] (* _Michael De Vlieger_, Jan 31 2018 *)
%o A072942 (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)))
%o A072942 (PARI) isok(n, x) = {fordiv(n, d, if (! isprime(polcyclo(d, x)), return(0));); return(1);}
%o A072942 a(n) = {my(x=2); while (! isok(n, x), x++); x;} \\ _Michel Marcus_, Jan 31 2018
%Y A072942 Cf. A000005, A001222, A008864, A014574, A070737.
%K A072942 nonn
%O A072942 1,1
%A A072942 _Phil Carmody_, Aug 12 2002
%E A072942 Corrected and extended by _Don Reble_, Feb 03 2014
%E A072942 Edited by _N. J. A. Sloane_, Mar 01 2014 at the suggestion of _Phil Carmody_ and _Don Reble_