cp's OEIS Frontend

A380757 Powers of primes that have a primitive root.

%I A380757 #21 Apr 01 2025 03:28:30
%S A380757 1,2,3,4,5,7,9,11,13,17,19,23,25,27,29,31,37,41,43,47,49,53,59,61,67,
%T A380757 71,73,79,81,83,89,97,101,103,107,109,113,121,125,127,131,137,139,149,
%U A380757 151,157,163,167,169,173,179,181,191,193,197,199,211,223,227,229
%N A380757 Powers of primes that have a primitive root.
%C A380757 Proper subset of A033948.
%C A380757 A046022 is a proper subset of this sequence.
%H A380757 Michael De Vlieger, <a href="/A380757/b380757.txt">Table of n, a(n) for n = 1..10000</a>
%F A380757 Union of {1, 2, 4} and A061345.
%F A380757 This sequence is A000961 without A000079(k) for k > 2.
%F A380757 A033948 = union of {a(n)} and {2*a(n)} without 8 = union of {a(n)} and A278568, where {a(n)} represents this sequence.
%F A380757 Intersection of A000961 and A033948.
%F A380757 Define c(m) to be the number of terms that do not exceed m. Then for m >= 4, c(m) = 3 + (Sum_{k = 1..floor(log_2(m))} pi(floor(m^(1/k)))) - floor(log_2(m)) = 3 + A065515(m) - A113473(m).
%t A380757 With[{nn = 2^8},
%t A380757   Complement[#, Array[2^# &, Floor@ Log2[#[[-1]]] + 2, 3]] &@
%t A380757   Union[{1}, Prime@ Range@ PrimePi[#[[-1]] ], #] &@
%t A380757   Select[Union@ Flatten@
%t A380757     Table[a^2*b^3, {b, Surd[#, 3]}, {a, Sqrt[nn/b^3]}],
%t A380757     PrimePowerQ] ]
%o A380757 (Python)
%o A380757 from sympy import primepi, integer_nthroot
%o A380757 def A380757(n):
%o A380757     def bisection(f,kmin=0,kmax=1):
%o A380757         while f(kmax) > kmax: kmax <<= 1
%o A380757         kmin = kmax >> 1
%o A380757         while kmax-kmin > 1:
%o A380757             kmid = kmax+kmin>>1
%o A380757             if f(kmid) <= kmid:
%o A380757                 kmax = kmid
%o A380757             else:
%o A380757                 kmin = kmid
%o A380757         return kmax
%o A380757     def f(x): return n if x<6 else int(n+x-3-sum(primepi(integer_nthroot(x,k)[0])-1 for k in range(1,x.bit_length())))
%o A380757     return bisection(f,n,n) # _Chai Wah Wu_, Feb 03 2025
%Y A380757 Cf. A000079, A000961, A033948, A046022, A061345, A278568.
%K A380757 nonn,easy
%O A380757 1,2
%A A380757 _Michael De Vlieger_, Feb 01 2025