login
Number of squarefree integers not exceeding 2^n.
29

%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&amp;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