cp's OEIS Frontend

A268629 Primes p that have no squareful primitive roots less than p.

%I A268629 #23 Sep 15 2022 06:27:56
%S A268629 3,5,7,13,17,19,23,31,41,43,47,61,71,73,79,97,103,127,191,193,223,239,
%T A268629 241,311,313,337,409,433,439,457,479,601,719,769,839,911,1009,1031,
%U A268629 1033,1129,1151,1201,1249,1319,1321,1559,1801,2089,2281,2521,2689,2999,3049,3361,3529,3889
%N A268629 Primes p that have no squareful primitive roots less than p.
%H A268629 Robert Israel, <a href="/A268629/b268629.txt">Table of n, a(n) for n = 1..114</a>
%H A268629 Stephen D. Cohen and Tim Trudgian, <a href="http://arxiv.org/abs/1602.02440">On the least square-free primitive root modulo p</a>, arXiv:1602.02440 [math.NT], 2016.
%e A268629 The primitive roots of 7 less than 7 are 3 and 5. None of them are squareful so 7 is in the sequence.
%e A268629 8 is a primitive root of 11, and 8 is squareful, so 11 is not in the sequence.
%p A268629 N:= 10^6: # for terms <= N
%p A268629 S:= {1}: p:= 1:
%p A268629 do
%p A268629   p:= nextprime(p);
%p A268629   if p^2 > N then break fi;
%p A268629   S:= S union map(t -> seq(t*p^i, i=2..floor(log[p](N/t))), select(`<=`,S,N/p^2));
%p A268629 od:
%p A268629 S:= sort(convert(S,list)):
%p A268629 nS:= nops(S):
%p A268629 filter:= proc(p) local i;
%p A268629   if not isprime(p) then return false fi;
%p A268629   for i from 1 to nS while S[i] < p do
%p A268629     if numtheory:-order(S[i],p) = p-1 then return false fi
%p A268629   od;
%p A268629   true
%p A268629 end proc:
%p A268629 select(filter, [seq(i,i=3..N,2)]); # _Robert Israel_, Oct 27 2020
%t A268629 selQ[p_] := NoneTrue[PrimitiveRootList[p], #<p && AllTrue[FactorInteger[#], #[[2]] >= 2&]&];
%t A268629 Select[Prime[Range[2, 500]], selQ] (* _Jean-François Alcover_, Sep 28 2018 *)
%o A268629 (PARI) ar(p) = my(r, pr, j); r=vector(eulerphi(p-1)); pr=znprimroot(p); for(i=1, p-1, if(gcd(i, p-1)==1, r[j++]=lift(pr^i))); vecsort(r) ; \\ from A060749
%o A268629 isok(p) = {my(v = ar(p)); for (i=1, #v, if (ispowerful(v[i]), return(0));); 1;}
%o A268629 lista(nn) = forprime(p=1, nn, if (isok(p), print1(p, ", ")));
%o A268629 (Python)
%o A268629 from functools import cache
%o A268629 from math import gcd
%o A268629 from itertools import count, islice
%o A268629 from sympy import factorint, prime, n_order
%o A268629 @cache
%o A268629 def is_squareful(n): return n == 1 or min(factorint(n).values()) > 1
%o A268629 def A268629_gen(): # generator of terms
%o A268629     for n in count(1):
%o A268629         p = prime(n)
%o A268629         for i in range(1,p):
%o A268629             if gcd(i,p) == 1 and is_squareful(i) and n_order(i, p)==p-1:
%o A268629                 break
%o A268629         else:
%o A268629             yield p
%o A268629 A268629_list = list(islice(A268629_gen(),20)) # _Chai Wah Wu_, Sep 14 2022
%Y A268629 Cf. A001694, A001918, A060749.
%K A268629 nonn
%O A268629 1,1
%A A268629 _Michel Marcus_, Feb 09 2016