|
Search: id:A143658
|
|
|
| A143658 |
|
Number of square-free integers not exceeding 2^n. |
|
+0
6
|
|
| 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; listen)
|
|
|
OFFSET
|
0,2
|
|
|
COMMENT
|
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
|
G. P. Michon, Table of n, a(n) for n=0..56
Project Euler, Problem 193: Squarefree Numbers
G. P. Michon, On the number of squarefree integers not exceeding N. [From Gerard P. Michon (g.michon(AT)att.net), Apr 30 2009]
|
|
FORMULA
|
a(n) = Sum for i = 1 to 2^(n/2) of A008683(i)*floor(sqrt(2^n/i^2)) [From Gerard P. Michon (g.michon(AT)att.net), Apr 30 2009]
The limit of a(n)/2^n is 6/pi^2. [From Gerard P. Michon (g.michon(AT)att.net), Apr 30 2009]
|
|
EXAMPLE
|
a(4)=11 since there are the 11 square-free 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 (rgwv(AT)rgwv.com), Aug 31 2008
|
|
PROGRAM
|
(PARI) print1(s=1); for(p=1, 20, print1(", ", s+=sum(k=2^(p-1)+1, 2^p, issquarefree(k))))
|
|
CROSSREFS
|
Cf. A005117, A071172, A053462.
Sequence in context: A054177 A141435 A096080 this_sequence A005230 A030037 A077078
Adjacent sequences: A143655 A143656 A143657 this_sequence A143659 A143660 A143661
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
M. F. Hasler (Maximilian.Hasler(AT)gmail.com), Aug 28 2008
|
|
EXTENSIONS
|
5 more terms from Robert G. Wilson v (rgwv(AT)rgwv.com), Aug 31 2008
More terms from Alexis Olson (AlexisOlson(AT)gmail.com), Nov 08 2008
|
|
|
Search completed in 0.002 seconds
|
