Page **1** of **1**

### Counting constrained squarefree numbers

Posted: **Thu Jan 21, 2021 1:12 am**

by **castrate**

As is known to all, the numbers of squarefree numbers below N can be computed in $O(\sqrt{N})$ time.

Now we consider numbers which are both squarefree and NOT divisible by 3 and 5.

For instance, there are 20 these numbers below 50, namely 1,2,7,11,13,14,17,19,22,23,26,29,31,34,37,38,41,43,46,47.

So can we count these numbers below N in $O(\sqrt{N})$ time? I attempted to use inclusion-exclusion, but failed.

### Re: Counting constrained squarefree numbers

Posted: **Thu Jan 21, 2021 6:24 am**

by **MuthuVeerappanR**

The same idea works for this case too. If I'm not wrong, you only have to learn to use the idea from

**Problem 1** (

View Problem).

### Re: Counting constrained squarefree numbers

Posted: **Thu Jan 21, 2021 8:26 am**

by **pjt33**

Let $d$ be a squarefree number, $S(n)$ count the squarefree numbers up to $n$, $S_d(n)$ count the squarefree numbers up to $n$ which are multiples of $d$.

The numbers counted by $S_d$ are in bijection with the squarefree numbers up to $\lfloor \frac{n}{d} \rfloor$ which are *not* multiples of $d$, so $S_d(n) = S(\lfloor \frac{n}{d} \rfloor) - S_d(\lfloor \frac{n}{d} \rfloor)$. Expand the last term and you get $$S_d(n) = \sum_{k=1}^{\log_d n} (-1)^{k+1} S\left(\left\lfloor \tfrac{n}{d^k} \right\rfloor\right)$$ which can be calculated in $O(\sqrt{n})$ even if no intermediate calculations can be shared.

Then, as Muthu observed, the same inclusion-exclusion as problem 1 can be used.

### Re: Counting constrained squarefree numbers

Posted: **Thu Jan 21, 2021 9:52 am**

by **castrate**

It seems that the formula above only holds when d is prime. For example, take d=6 and n=100, the formula yields $S_6(100)=11-2=9$, but actually $S_6(100)=5$.

In fact, for squarefree $d=p_1 p_2$, the formula should be $S_{p_1 p_2}(n)=S(\lfloor\frac{n}{p_1 p_2}\rfloor)-S_{p_1}(\lfloor\frac{n}{p_1 p_2}\rfloor)-S_{p_2}(\lfloor\frac{n}{p_1 p_2}\rfloor)+S_{p_1 p_2}(\lfloor\frac{n}{p_1 p_2}\rfloor)$

### Re: Counting constrained squarefree numbers

Posted: **Thu Jan 21, 2021 12:40 pm**

by **pjt33**

castrate wrote: ↑Thu Jan 21, 2021 9:52 amIt seems that the formula above only holds when d is prime.

Oops. You're quite correct. Where I said "which are

*not* multiples of $d$" I should have said "which are coprime with $d$". Then an inclusion-exclusion follows as you indicate. The conclusion that this gives an approach which finds constrained squarefree numbers in the same asymptotic time (in $n$) as finding squarefree numbers still holds.