A085971 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,1

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

LINKS

Table of n, a(n) for n=1..68.

FORMULA

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

MATHEMATICA

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

PROG

(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

CROSSREFS

Sequence in context: A089105 A028769 A094784 * A175082 A007916 A052485

Adjacent sequences: A085968 A085969 A085970 * A085972 A085973 A085974

KEYWORD

nonn,easy

AUTHOR

Reinhard Zumkeller, Jul 06 2003

STATUS

approved