A076411 Number of perfect powers < n.

0, 1, 1, 1, 2, 2, 2, 2, 3, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12

Offset: 1

Author

Zak Seidov, Oct 09 2002

Keywords

• nonn

Comments

Perfect powers are in A001597. The function a(n) increases much more slowly than pi(n): e.g., a(1765)=54 and pi(1765)=274. See also A076412.

a(n) >= A000196(n-1). - Robert Israel, Jul 31 2015

This is essentially the same as A069623 which is the main entry, see there for more formulas. - M. F. Hasler, Aug 16 2015

Examples

			a(9)=3 because there are 3 perfect powers less than 9: 1,4,8.
		

Links

• Harvey P. Dale, Table of n, a(n) for n = 1..1000

Crossrefs

A069623(n) = a(n+1) is the main entry.

Cf. A001597, A076412, A075802, A096623.

Programs

Mathematica

Join[{0},Accumulate[Table[If[GCD@@FactorInteger[n][[All,2]]>1,1,0],{n,90}]]+1] (* Harvey P. Dale, Mar 19 2020 *)

PARI

a(n)=n--; n-sum(k=1,logint(n,2), moebius(k)*(sqrtnint(n,k)-1)) \\ Charles R Greathouse IV, Jul 21 2017

Python

from sympy import mobius, integer_nthroot
def A076411(n): return int(n-1+sum(mobius(k)*(1-integer_nthroot(n-1,k)[0]) for k in range(1,(n-1).bit_length()))) # Chai Wah Wu, Dec 03 2024

Formula

a(n) = n^(1/2) + n^(1/3) + n^(1/5) - n^(1/6) + n^(1/7) - n^(1/10) + O(n^(1/11)). - Charles R Greathouse IV, Aug 14 2015