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 inclusionexclusion, but failed.
Counting constrained squarefree numbers

 Posts: 495
 Joined: Sun Mar 22, 2015 2:30 pm
 Location: India
 Contact:
Re: Counting constrained squarefree numbers
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).
It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.
Re: Counting constrained squarefree numbers
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 inclusionexclusion as problem 1 can be used.
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 inclusionexclusion as problem 1 can be used.
Re: Counting constrained squarefree numbers
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)=112=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)$
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
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 inclusionexclusion 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.