A085971 Union of primes and numbers that are not prime powers (A000040, A024619).

2, 3, 5, 6, 7, 10, 11, 12, 13, 14, 15, 17, 18, 19, 20, 21, 22, 23, 24, 26, 28, 29, 30, 31, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78

Offset: 1

Author

Reinhard Zumkeller, Jul 06 2003

Keywords

• nonn
• easy

Comments

Complement of A025475;

A085972(n) = Max{k: a(k)<=n};

different from A007916 and A052485, as a(28)=36;

A085818(a(n)) = A000040(n).

Programs

Mathematica

With[{nn=100},Union[Join[Prime[Range[PrimePi[nn]]],DeleteCases[Range[2,80], ?(PrimePowerQ[#]&)]]]] (* _Harvey P. Dale, May 15 2019 *)

PARI

is(n)=isprimepower(n)<2 && n>1 \\ Charles R Greathouse IV, Oct 19 2015

Python

from sympy import primepi, integer_nthroot
def A085971(n):
    def f(x): return int(n+sum(primepi(integer_nthroot(x,k)[0]) for k in range(2,x.bit_length())))
    kmin, kmax = 1,2
    while f(kmax) >= kmax:
        kmax <<= 1
    while True:
        kmid = kmax+kmin>>1
        if f(kmid) < kmid:
            kmax = kmid
        else:
            kmin = kmid
        if kmax-kmin <= 1:
            break
    return kmax # Chai Wah Wu, Aug 20 2024

Formula

a(n) = n + o(sqrt n). - Charles R Greathouse IV, Oct 19 2015