cp's OEIS Frontend

A143658 Number of squarefree integers not exceeding 2^n.

%I A143658 #60 Aug 07 2024 22:29:38
%S A143658 1,2,3,6,11,20,39,78,157,314,624,1245,2491,4982,9962,19920,39844,
%T A143658 79688,159360,318725,637461,1274918,2549834,5099650,10199301,20398664,
%U A143658 40797327,81594626,163189197,326378284,652756722,1305513583,2611027094
%N A143658 Number of squarefree integers not exceeding 2^n.
%C A143658 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 A143658 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 A143658 Project Euler, <a href="http://projecteuler.net/index.php?section=problems&amp;id=193">Problem 193: Squarefree Numbers</a>
%H A143658 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 A143658 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 A143658 The limit of a(n)/2^n is 6/Pi^2. - _Gerard P. Michon_, Apr 30 2009
%e A143658 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 A143658 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 A143658 (PARI) print1(s=1);for(p=1,20,print1(", ",s+=sum(k=2^(p-1)+1, 2^p, issquarefree(k))))
%o A143658 (PARI) a(n)=sum(d=1,sqrtint(n=2^n),moebius(d)*n\d^2) \\ _Charles R Greathouse IV_, Nov 14 2012
%o A143658 (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 A143658 (Python)
%o A143658 from math import isqrt
%o A143658 from sympy import mobius
%o A143658 def A143658(n):
%o A143658     m = 1<<n
%o A143658     return sum(mobius(k)*(m//k**2) for k in range(1,isqrt(m)+1)) # _Chai Wah Wu_, Jun 01 2024
%Y A143658 Cf. A005117, A013928, A071172, A053462.
%K A143658 nonn
%O A143658 0,2
%A A143658 _M. F. Hasler_, Aug 28 2008
%E A143658 5 more terms from _Robert G. Wilson v_, Aug 31 2008
%E A143658 More terms from Alexis Olson (AlexisOlson(AT)gmail.com), Nov 08 2008