A380757 Powers of primes that have a primitive root.

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, 71, 73, 79, 81, 83, 89, 97, 101, 103, 107, 109, 113, 121, 125, 127, 131, 137, 139, 149, 151, 157, 163, 167, 169, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229

Offset: 1

Author

Michael De Vlieger, Feb 01 2025

Keywords

• nonn
• easy

Comments

Proper subset of A033948.

A046022 is a proper subset of this sequence.

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000079, A000961, A033948, A046022, A061345, A278568.

Programs

Mathematica

With[{nn = 2^8},
  Complement[#, Array[2^# &, Floor@ Log2[#[[-1]]] + 2, 3]] &@
  Union[{1}, Prime@ Range@ PrimePi[#[[-1]] ], #] &@
  Select[Union@ Flatten@
    Table[a^2*b^3, {b, Surd[#, 3]}, {a, Sqrt[nn/b^3]}],
    PrimePowerQ] ]

Python

from sympy import primepi, integer_nthroot
def A380757(n):
    def bisection(f,kmin=0,kmax=1):
        while f(kmax) > kmax: kmax <<= 1
        kmin = kmax >> 1
        while kmax-kmin > 1:
            kmid = kmax+kmin>>1
            if f(kmid) <= kmid:
                kmax = kmid
            else:
                kmin = kmid
        return kmax
    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())))
    return bisection(f,n,n) # Chai Wah Wu, Feb 03 2025

Formula

Union of {1, 2, 4} and A061345.

This sequence is A000961 without A000079(k) for k > 2.

A033948 = union of {a(n)} and {2*a(n)} without 8 = union of {a(n)} and A278568, where {a(n)} represents this sequence.

Intersection of A000961 and A033948.

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