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,5

Comments

Powerful numbers are given by A001694.

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.

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

Example

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

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}]]

Prog

(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

Crossrefs

Cf. A001597, A001694, A076411, A090699.

Partial sums of A112526.

Sequence in context: A085501 A069623 A076411 * A309196 A243283 A243284

Adjacent sequences: A217035 A217036 A217037 * A217039 A217040 A217041

Keyword

nonn

Author

Jayanta Basu, Apr 07 2013

Status

approved