Counting constrained squarefree numbers

Arrangements, sorting, packing, partitions, critical path analysis, networks, graphs, ...
Post Reply
castrate
Posts: 23
Joined: Mon Aug 19, 2019 2:34 pm

Counting constrained squarefree numbers

Post 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. :(
MuthuVeerappanR
Posts: 492
Joined: Sun Mar 22, 2015 2:30 pm
Location: India
Contact:

Re: Counting constrained squarefree numbers

Post 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).
Image
It is not knowledge, but the act of learning, not possession but the act of getting there, which grants the greatest enjoyment.
pjt33
Posts: 68
Joined: Mon Oct 06, 2008 6:14 pm

Re: Counting constrained squarefree numbers

Post 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.
castrate
Posts: 23
Joined: Mon Aug 19, 2019 2:34 pm

Re: Counting constrained squarefree numbers

Post 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)$
pjt33
Posts: 68
Joined: Mon Oct 06, 2008 6:14 pm

Re: Counting constrained squarefree numbers

Post 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.
Post Reply