%I #60 Aug 07 2024 22:29:38
%S 1,2,3,6,11,20,39,78,157,314,624,1245,2491,4982,9962,19920,39844,
%T 79688,159360,318725,637461,1274918,2549834,5099650,10199301,20398664,
%U 40797327,81594626,163189197,326378284,652756722,1305513583,2611027094
%N Number of squarefree integers not exceeding 2^n.
%C Except for the first 2 terms, it would not make a difference to replace "not exceeding" by "less than": that sequence would start 0,1,3,6,11,20,39,78,...
%H Chai Wah Wu, <a href="/A143658/b143658.txt">Table of n, a(n) for n = 0..73</a> (terms 0..58 from Gerard P. Michon, terms 59..64 from Peter Polm)
%H Project Euler, <a href="http://projecteuler.net/index.php?section=problems&id=193">Problem 193: Squarefree Numbers</a>
%H G. P. Michon, <a href="http://www.numericana.com/answer/counting.htm#euler193">On the number of squarefree integers not exceeding N</a>. - _Gerard P. Michon_, Apr 30 2009
%F a(n) = Sum for i = 1 to 2^(n/2) of A008683(i)*floor(2^n/i^2). - _Gerard P. Michon_, Apr 30 2009
%F The limit of a(n)/2^n is 6/Pi^2. - _Gerard P. Michon_, Apr 30 2009
%e a(4) = 11 since there are the 11 squarefree integers {1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15} not exceeding 2^4=16.
%t c = 0; k = 1; lst = {1}; Do[ While[k <= 2^n, If[ SquareFreeQ@k, c++ ]; k++ ]; AppendTo[lst, c], {n, 27}] (* _Robert G. Wilson v_, Aug 31 2008 *)
%o (PARI) print1(s=1);for(p=1,20,print1(", ",s+=sum(k=2^(p-1)+1, 2^p, issquarefree(k))))
%o (PARI) a(n)=sum(d=1,sqrtint(n=2^n),moebius(d)*n\d^2) \\ _Charles R Greathouse IV_, Nov 14 2012
%o (PARI) a(n)=my(s); forsquarefree(d=1,sqrtint(n=2^n), s += n\d[1]^2*moebius(d)); s \\ _Charles R Greathouse IV_, Jan 08 2018
%o (Python)
%o from math import isqrt
%o from sympy import mobius
%o def A143658(n):
%o m = 1<<n
%o return sum(mobius(k)*(m//k**2) for k in range(1,isqrt(m)+1)) # _Chai Wah Wu_, Jun 01 2024
%Y Cf. A005117, A013928, A071172, A053462.
%K nonn
%O 0,2
%A _M. F. Hasler_, Aug 28 2008
%E 5 more terms from _Robert G. Wilson v_, Aug 31 2008
%E More terms from Alexis Olson (AlexisOlson(AT)gmail.com), Nov 08 2008