A076407 Sum of perfect powers <= n.

1, 1, 1, 5, 5, 5, 5, 13, 22, 22, 22, 22, 22, 22, 22, 38, 38, 38, 38, 38, 38, 38, 38, 38, 63, 63, 90, 90, 90, 90, 90, 122, 122, 122, 122, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 158, 207, 207, 207, 207, 207, 207, 207, 207, 207, 207, 207, 207, 207

Offset

1,4

Links

Robert Israel, Table of n, a(n) for n = 1..10000

Eric Weisstein's World of Mathematics, Perfect Powers.

Formula

a(n) = 1 - Sum_{k=2..floor(log_2(n))} mu(k) * (F(k, floor(n^(1/k))) - 1), where F(k, n) = Sum_{j=1..n} j^k = (Bernoulli(k+1, n+1) - Bernoulli(k+1, 1))/(k+1). - Daniel Suteu, Aug 19 2023

Example

Sum of the 8 perfect powers <= 32: a(32) = 1+4+8+9+16+25+27+32 = 122.

Maple

N:= 100: # for a(1)..a(N)
V:= Vector(N, 1):
pps:= {seq(seq(x^k, k=2..floor(log[x](N))), x=2..floor(sqrt(N)))}:
for y in pps do
   V[y..N]:= V[y..N] +~ y
od:
convert(V, list); # Robert Israel, Oct 19 2023

Prog

(PARI)
F(k, n) = (subst(bernpol(k+1), x, n+1) - subst(bernpol(k+1), x, 1)) / (k+1);
a(n) = 1 - sum(k=2, logint(n, 2), moebius(k) * (F(k, sqrtnint(n, k)) - 1)); \\ Daniel Suteu, Aug 19 2023

Crossrefs

Cf. A001597, A076408, A069623.

Sequence in context: A071577 A003870 A304681 * A134701 A291655 A078097

Adjacent sequences: A076404 A076405 A076406 * A076408 A076409 A076410

Keyword

nonn

Author

Reinhard Zumkeller, Oct 09 2002

Status

approved