# Formula for numbers divisible in an interval

Assume we have three natural numbers $$x$$, $$y$$, and $$z$$, with $$z>y>x$$.

I want to find a formula, which gives us the number of natural numbers divisible by $$x$$, in the interval $$[y,z]$$.

From some observation, I got the formula

$$N=\Big\lfloor\frac zx\Big\rfloor-\Big\lfloor \frac yx\Big\rfloor$$

This was working pretty good...

\begin{align}[100,999]÷3&=300 \\ [100,999]÷6&=150 \\ [100,999]÷42&=21\end{align}

...until it didn't.

$$[100,999]÷2=450$$

whereas the formula gives $$449$$.

I think this error is because $$100$$ is already divisible by $$2$$.

My question is how can I modify the formula so that that I can account for the case where $$y$$ is already divisible by $$x$$. It seems that for such cases

$$N=\Big\lfloor\frac zx\Big\rfloor-\Big\lfloor\frac yx\Big\rfloor+1$$

works, but I would prefer a formula which accounts for both cases, whether $$y$$ is divisible by $$x$$, or not.

Though if such a formula is complicated, then it can't be helped.

I also noted that if we take the divisible case, then the condition on the numbers would've to be changed to $$z>y\ge x$$.

• You may want to turn a floor into a ceiling Commented Aug 4, 2023 at 8:13
• @Henry If you mean changing the later one, I think that'll give incorrect results for other cases. If both, then it doesn't affect the resultant value. Commented Aug 4, 2023 at 8:54
• If $x=1$ then you would want $z-y+1$ if $z$ and $y$ are integers; more generally you would want $\lfloor z\rfloor-\lceil y \rceil +1$. So reintroducing $x$ you want $\lfloor\frac zx \rfloor - \lceil\frac yx \rceil +1$ Commented Aug 4, 2023 at 9:25

If $$x=1$$ then you would want $$z-y+1$$ if $$z$$ and $$y$$ are integers; more generally you would want $$\lfloor z\rfloor-\lceil y \rceil +1$$. So, reintroducing $$x$$, try $$\bigg\lfloor\frac zx \bigg\rfloor - \bigg\lceil\frac yx \bigg\rceil +1$$

Examples:

 x   y     z          function

3  100   999     333 - 34 + 1 = 300
3   99   999     333 - 33 + 1 = 301
3  100   998     332 - 34 + 1 = 299
3   99   998     332 - 33 + 1 = 300
2  100   999     499 - 50 + 1 = 450
1  100   999     999 -100 + 1 = 900


as you might hope

• Just...wow! Quite wonderful, thanks to integer discontinuity of $\lfloor\,\rfloor$ and $\lceil\,\rceil$. Thanks! Commented Aug 11, 2023 at 12:16

Here is an idea (probably can be simplified): find the first multiple of $$x$$ in the interval, say $$w$$ and then reduce to the interval $$[1,z-w+1]$$. Since $$w=\left\lceil\frac{y}{x}\right\rceil x$$ we can get the following formula $$N = \left\lceil\frac{z-\left\lceil\frac{y}{x}\right\rceil x + 1}{x}\right\rceil= \left\lceil\frac{z+1}{x}-\left\lceil\frac{y}{x}\right\rceil\right\rceil$$. Note that here you would need to take the maximum between the result and $$0$$ since you may end up with negative numbers if $$z-y+1 hence a complete formulation would be $$N = \text{max}\left(\left\lceil\frac{z+1}{x}-\left\lceil\frac{y}{x}\right\rceil\right\rceil,0\right)$$.

• Thanks a lot! This seems to work fine. I'll wait some time to see if a better answer gets posted, until I accept your answer. Commented Aug 4, 2023 at 9:06

Here is a way to do it using only the floor function:

For natural numbers $$n$$ and $$k$$, There are $$\left\lfloor \frac{n}{k} \right\rfloor$$ multiples of $$k$$ on the interval $$[1,n]$$.

In the given situation, we would take the number of multiples of $$x$$ on the interval $$[1,z]$$ and subtract off the number of multiples of $$x$$ on the interval $$[1,y-1]$$. This will then include multiples from $$y$$ to $$z$$ inclusive.

So the number of multiples of $$x$$ in $$[y,z]$$ is given by: $$\left\lfloor\frac{z}{x}\right\rfloor - \left\lfloor\frac{y-1}{x}\right\rfloor$$