|
|
A143658
|
|
Number of squarefree integers not exceeding 2^n.
|
|
26
|
|
|
1, 2, 3, 6, 11, 20, 39, 78, 157, 314, 624, 1245, 2491, 4982, 9962, 19920, 39844, 79688, 159360, 318725, 637461, 1274918, 2549834, 5099650, 10199301, 20398664, 40797327, 81594626, 163189197, 326378284, 652756722, 1305513583, 2611027094
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
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,...
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
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.
|
|
MATHEMATICA
|
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 *)
|
|
PROG
|
(PARI) print1(s=1); for(p=1, 20, print1(", ", s+=sum(k=2^(p-1)+1, 2^p, issquarefree(k))))
(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
(Python)
from math import isqrt
from sympy import mobius
m = 1<<n
return sum(mobius(k)*(m//k**2) for k in range(1, isqrt(m)+1)) # Chai Wah Wu, Jun 01 2024
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,changed
|
|
AUTHOR
|
|
|
EXTENSIONS
|
More terms from Alexis Olson (AlexisOlson(AT)gmail.com), Nov 08 2008
|
|
STATUS
|
approved
|
|
|
|