cp's OEIS Frontend

A193305 Composite numbers of the form 4, p^m, or 2*p^m for p an odd prime. All composites that have a primitive root.

%I A193305 #40 Feb 25 2025 07:17:00
%S A193305 4,6,9,10,14,18,22,25,26,27,34,38,46,49,50,54,58,62,74,81,82,86,94,98,
%T A193305 106,118,121,122,125,134,142,146,158,162,166,169,178,194,202,206,214,
%U A193305 218,226,242,243,250,254,262,274,278,289,298,302,314,326,334,338,343
%N A193305 Composite numbers of the form 4, p^m, or 2*p^m for p an odd prime. All composites that have a primitive root.
%C A193305 Nonprime k such that the multiplicative group modulo k is cyclic.  Nonprime terms of A033948 (omitting the initial term 1). - _Joerg Arndt_, Aug 07 2011
%C A193305 a(n) has a primitive root for any n. - _Arkadiusz Wesolowski_, Sep 06 2012 [See, e.g., the Niven et al. reference. - _Wolfdieter Lang_, Jan 18 2017]
%D A193305 Ivan Niven, Herbert S. Zuckerman and Hugh L. Montgomery, An Introduction to the Theory Of Numbers, Fifth Edition, John Wiley and Sons, Inc., NY 1991, Theorem 2.41, p. 104.
%H A193305 T. D. Noe, <a href="/A193305/b193305.txt">Table of n, a(n) for n = 1..10000</a>
%H A193305 Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, relation (39.7-13) on page 779.
%t A193305 lim = 500; t = {4}; Do[p = Prime[n]; k = 1; While[p^k <= lim, If[k > 1, AppendTo[t, p^k]]; If[2*p^k <= lim, AppendTo[t, 2*p^k]]; k++], {n, 2, PrimePi[lim/2]}]; Sort[t]; (* _T. D. Noe_, Sep 06 2012 *)
%o A193305 (PARI) for (n=2, 555, if ( isprime(n), next() ); if ( 1 == #(znstar(n)[3]), print1(n,", ") ); );  /* _Joerg Arndt_, Aug 07 2011 */
%o A193305 (Python)
%o A193305 from sympy import primepi, integer_nthroot
%o A193305 def A193305(n):
%o A193305     def bisection(f,kmin=0,kmax=1):
%o A193305         while f(kmax) > kmax: kmax <<= 1
%o A193305         kmin = kmax >> 1
%o A193305         while kmax-kmin > 1:
%o A193305             kmid = kmax+kmin>>1
%o A193305             if f(kmid) <= kmid:
%o A193305                 kmax = kmid
%o A193305             else:
%o A193305                 kmin = kmid
%o A193305         return kmax
%o A193305     def f(x): return int(n+x-(x>=4)-sum(primepi(integer_nthroot(x,k)[0])-1 for k in range(2,x.bit_length()))-sum(primepi(integer_nthroot(x>>1,k)[0])-1 for k in range(1,x.bit_length()-1)))
%o A193305     return bisection(f,n,n) # _Chai Wah Wu_, Feb 24 2025
%Y A193305 Cf. A033948, A033949 (composites without primitive root). A279398.
%K A193305 nonn
%O A193305 1,1
%A A193305 _Warren Breslow_, Jul 21 2011
%E A193305 More terms from _Joerg Arndt_, Aug 07 2011
%E A193305 Name corrected and augmented by _Wolfdieter Lang_, Jan 18 2017