A077643 Number of squarefree integers in closed interval [2^n, -1 + 2*2^n], i.e., among 2^n consecutive numbers beginning with 2^n.

1, 2, 3, 5, 9, 19, 39, 79, 157, 310, 621, 1246, 2491, 4980, 9958, 19924, 39844, 79672, 159365, 318736, 637457, 1274916, 2549816, 5099651, 10199363, 20398663, 40797299, 81594571, 163189087, 326378438, 652756861, 1305513511, 2611026987, 5222053970, 10444108084

Offset: 0

Author

Labos Elemer, Nov 14 2002

Keywords

• nonn

Comments

Number of squarefree numbers with binary expansion of length n, or with n bits. The sum of these numbers is given by A373123. - Gus Wiseman, Jun 02 2024

Examples

			For n=4: among the 16 numbers of {16, ..., 31}, nine are squarefree [17, 19, 21, 22, 23, 26, 29, 30, 31], so a(4) = 9.
		

Links

• Amiram Eldar, Table of n, a(n) for n = 0..63 (calculated from the b-file at A143658)

Crossrefs

Cf. A077641, A077642.

Partial sums (except first term) are A143658.

Run-lengths of A372475.

The minimum is A372683, delta A373125, indices A372540.

The maximum is A372889 (except at n=1), delta A373126, indices A143658.

Row-sums are A373123.

A005117 lists squarefree numbers, first differences A076259.

A053797 gives nonempty lengths of exclusive gaps between squarefree numbers.

A029837 counts bits, row-lengths of A030190 and A030308.

For primes between powers of 2:

- sum A293697

- length A036378 or A162145

- min A104080 or A014210, delta A092131, indices A372684

- max A014234, delta A013603, indices A007053

For squarefree numbers between primes:

- sum A373197

- length A373198 = A061398 - 1

- min A000040

- max A112925 (delta A240473), opposite A112926 (delta A240474)

Cf. A010036, A029931, A035100, A049093-A049096, A372473 (firsts of A372472), A372541 (firsts of A372433).

Programs

Mathematica

Table[Apply[Plus, Table[Abs[MoebiusMu[2^w+j]], {j, 0, 2^w-1}]], {w, 0, 15}]
(* second program *)
Length/@Split[IntegerLength[Select[Range[10000],SquareFreeQ],2]]//Most (* Gus Wiseman, Jun 02 2024 *)

PARI

{ a(n) = sum(m=1,sqrtint(2^(n+1)-1), moebius(m) * ((2^(n+1)-1)\m^2 - (2^n-1)\m^2) ) } \\ Max Alekseyev, Oct 18 2008

Formula

a(n) = Sum_{j=0..-1+2^n} abs(mu(2^n + j)).

a(n)/2^n approaches 1/zeta(2), so limiting sequence is floor(2^n/zeta(2)), n >= 0. - Wouter Meeussen, May 25 2003

Extensions

More terms from Mark Hudson (mrmarkhudson(AT)hotmail.com), Feb 12 2003

More terms from Wouter Meeussen, May 25 2003

a(25)-a(32) from Max Alekseyev, Oct 18 2008

a(33)-a(34) from Amiram Eldar, Jul 17 2024