A217038 Number of powerful numbers < 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, 12, 12, 12, 12, 12

Offset: 1

Author

Jayanta Basu, Apr 07 2013

Keywords

• nonn

Comments

Powerful numbers are given by A001694.

Examples

			a(10)=4 since there are exactly 4 powerful numbers (1,4,8,9) less than 10.
		

Links

• Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
• Paul Erdős and George Szekeres, Über die Anzahl der Abelschen Gruppen gegebener Ordnung und über ein verwandtes zahlentheoretisches Problem, Acta Sci. Math. (Szeged), Vol. 7, No. 2 (1935), pp. 95-102.
• Solomon W. Golomb, Powerful numbers, Amer. Math. Monthly, Vol. 77, No. 8 (1970), pp. 848-852.

Crossrefs

Cf. A001597, A001694, A076411, A090699.

Partial sums of A112526.

Programs

Mathematica

PowQ[n_] := Cases[FactorInteger[n], {p_, 1} -> p] == {}; Q[n_] := Length[Join[{1}, Select[Range[n - 1], PowQ[#] &]]] ; Join[{0}, Table[Q[n], {n, 2, 100}]]

PARI

g(n,fe=factor(n)[,2])=prod(i=1,#fe, (fe[i]+2)\2 - (fe[i]+2)\3)
a(n)=my(v=List(),t); n--; for(m=2,sqrtnint(n,6), for(y=1,sqrtnint(n\m^6,3), t=(m^2*y)^3; for(x=1,sqrtint(n\t), listput(v,t*x^2)))); v=Set(v); sum(y=1,sqrtnint(n,3), sqrtint(n\y^3))-sum(i=1,#v, g(v[i])-1) \\ Charles R Greathouse IV, Jul 31 2017

PARI

first(n)=my(v=vector(n),s=1); if(n>1, v[2]=1); forfactored(k=2,n-1, if(vecmin(k[2][,2])>1, s++); v[k[1]+1]=s); v \\ Charles R Greathouse IV, Jul 31 2017

PARI

a(n)=my(s); n--; forsquarefree(k=1,sqrtnint(n,3), s+=sqrtint(n\k[1]^3)); s \\ Charles R Greathouse IV, Dec 12 2022

Python

from math import isqrt
from sympy import mobius, integer_nthroot
def A217038(n):
    def squarefreepi(n): return int(sum(mobius(k)*(n//k**2) for k in range(1, isqrt(n)+1)))
    c, l = 0, 0
    j = isqrt(n-1)
    while j>1:
        k2 = integer_nthroot((n-1)//j**2,3)[0]+1
        w = squarefreepi(k2-1)
        c += j*(w-l)
        l, j = w, isqrt((n-1)//k2**3)
    c += squarefreepi(integer_nthroot(n-1,3)[0])-l
    return c # Chai Wah Wu, Sep 12 2024

Formula

a(n) = (zeta(3/2)/zeta(3)) * sqrt(n) + O(n^(1/3)) (Erdős and Szekeres, 1935; Golomb, 1970). - Amiram Eldar, Apr 06 2023