A256942 Number of odd squarefree numbers <= 2^n.

1, 1, 2, 4, 7, 13, 26, 52, 105, 209, 415, 830, 1661, 3321, 6641, 13279, 26565, 53123, 106237, 212488, 424973, 849945, 1699889, 3399761, 6799540, 13599124, 27198203, 54396423, 108792774, 217585510, 435171212, 870342371, 1740684723, 3481369358, 6962738693, 13925477442

Offset

0,3

Comments

Number of oddly squarefree (A122132) numbers in each new tier > 2^(n-1). - Travis Scott, Jan 14 2023

a(n) is also the number of even squarefree numbers <= 2^(n+1). - Amiram Eldar, Feb 20 2023

Links

Chai Wah Wu, Table of n, a(n) for n = 0..73 (terms 0..64 from Amiram Eldar)

Formula

a(n) = Sum_{j=0..n} (-1)^j*A143658(n-j).

a(n) = (2/3) * A143658(n) + (1/3) * Sum_{i=1..floor(2^(n/2))} A008683(i)*A065359(floor(2^n/i^2)).

a(n) + a(n+1) = A143658(n+1).

a(n) ~ 2^(n+2)/Pi^2. - Amiram Eldar, Feb 20 2023

Example

For n=4 there are 7 odd squarefree numbers <= 2^4, namely 1,3,5,7,11,13,15.
For oddly squarefree we have 2^3 < 10,11,12,13,14,15,16 <= 2^4.

Maple

g:= proc(n) option remember; local L ; L := convert(n, base, 2) ; (2*n - add( L[i]*(-1)^i, i=1..nops(L)))/3 ; end proc:
a:= n -> add(numtheory:-mobius(i)*g(floor(2^n/i^2)), i=1..floor(2^(n/2))):
seq(a(n), n=0..32);

Mathematica

A143658[n_] := Sum[MoebiusMu[i] Floor[2^n/i^2], {i, 1, 2^(n/2)}];
a[n_] := Sum[(-1)^j A143658[n-j], {j, 0, n}];
Table[a[n], {n, 0, 32}] (* Jean-François Alcover, Sep 22 2022 *)

Crossrefs

Cf. A008683, A039956, A056911, A065359, A122132, A143658.

Sequence in context: A293314 A023431 A025246 * A112740 A309050 A265580

Adjacent sequences: A256939 A256940 A256941 * A256943 A256944 A256945

Keyword

nonn

Author

Robert Israel, Apr 13 2015

Extensions

a(33)-a(35) from Amiram Eldar, Feb 20 2023

Status

approved