cp's OEIS Frontend

A076411 Number of perfect powers < n.

%I A076411 #43 Dec 03 2024 12:21:50
%S A076411 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,
%T A076411 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,
%U A076411 10,10,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,12,12,12,12
%N A076411 Number of perfect powers < n.
%C A076411 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.
%C A076411 a(n) >= A000196(n-1). - _Robert Israel_, Jul 31 2015
%C A076411 This is essentially the same as A069623 which is the main entry, see there for more formulas. - _M. F. Hasler_, Aug 16 2015
%H A076411 Harvey P. Dale, <a href="/A076411/b076411.txt">Table of n, a(n) for n = 1..1000</a>
%F A076411 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
%e A076411 a(9)=3 because there are 3 perfect powers less than 9: 1,4,8.
%t A076411 Join[{0},Accumulate[Table[If[GCD@@FactorInteger[n][[All,2]]>1,1,0],{n,90}]]+1] (* _Harvey P. Dale_, Mar 19 2020 *)
%o A076411 (PARI) a(n)=n--; n-sum(k=1,logint(n,2), moebius(k)*(sqrtnint(n,k)-1)) \\ _Charles R Greathouse IV_, Jul 21 2017
%o A076411 (Python)
%o A076411 from sympy import mobius, integer_nthroot
%o A076411 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
%Y A076411 A069623(n) = a(n+1) is the main entry.
%Y A076411 Cf. A001597, A076412, A075802, A096623.
%K A076411 nonn
%O A076411 1,5
%A A076411 _Zak Seidov_, Oct 09 2002