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.