A070228 - OEIS

%I #39 Aug 13 2024 11:20:55

%S 1,1,2,3,5,8,11,16,23,31,42,58,82,114,156,217,299,417,583,814,1136,

%T 1589,2224,3116,4369,6136,8623,12128,17064,24023,33839,47689,67227,

%U 94805,133738,188710,266351,376019,530941,749820,1059097,1496144,2113802,2986770,4220666

%N Number of perfect powers (A001597) not exceeding 2^n.

%H Amiram Eldar, <a href="/A070228/b070228.txt">Table of n, a(n) for n = 0..6643</a> (terms 0..1000 from Robert G. Wilson v)

%F a(n) = 1 - Sum_{k=2..n} Moebius(k)*floor(2^(n/k)-1). - _Robert G. Wilson v_, Jan 20 2015

%F a(n) = A188951(n) + 1 for n > 1. - _Amiram Eldar_, May 19 2022

%e How many powers are there not exceeding 2^4?: 1, 4, 8, 9, 16. Hence a(4) = 5.

%e a(22)=2224: there are 2224 powers not exceeding 2^22.

%t 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 *)

%o (PARI) a(n) = 1 - sum(k=2, n, moebius(k)*(sqrtnint(2^n,k)-1));

%o (Python)

%o from sympy import mobius, integer_nthroot

%o 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

%Y Cf. A070428, A188951.

%K nonn,easy

%O 0,3

%A _Donald S. McDonald_, May 14 2002

%E a(39)-a(44) from _Alex Ratushnyak_, Jan 02 2014