OFFSET
0,3
LINKS
Amiram Eldar, Table of n, a(n) for n = 0..6643 (terms 0..1000 from Robert G. Wilson v)
FORMULA
a(n) = 1 - Sum_{k=2..n} Moebius(k)*floor(2^(n/k)-1). - Robert G. Wilson v, Jan 20 2015
a(n) = A188951(n) + 1 for n > 1. - Amiram Eldar, May 19 2022
EXAMPLE
How many powers are there not exceeding 2^4?: 1, 4, 8, 9, 16. Hence a(4) = 5.
a(22)=2224: there are 2224 powers not exceeding 2^22.
MATHEMATICA
f[n_] := 1 - Sum[ MoebiusMu[x]*Floor[2^(n/x) - 1], {x, 2, n}]; Array[f, 44, 0] (* Robert G. Wilson v, Jan 20 2015 *)
PROG
(PARI) a(n) = 1 - sum(k=2, n, moebius(k)*(sqrtnint(2^n, k)-1));
(Python)
from sympy import mobius, integer_nthroot
def A070228(n): return int(1+sum(mobius(x)*(1-integer_nthroot(1<<n, x)[0]) for x in range(2, n+1))) # Chai Wah Wu, Aug 13 2024
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Donald S. McDonald, May 14 2002
EXTENSIONS
a(39)-a(44) from Alex Ratushnyak, Jan 02 2014
STATUS
approved