How to find k'th integer not divisible by n?

Question

Although this was a programming question I want the mathematical intuition behind it. So we were given two numbers $n$ and $k$. We were asked to find out $k{-th}$ number **not divisible** by $n$.

For example, $n=3$ and $k=7$. If we see numbers $1$ to $12$. $$1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12$$ Then $3,6,9$ are divisible by $3$ so we remove it. So we are left with $1, 2, 4, 5, 7, 8, 10, 11$. Clearly the $7th$ number not divisible by $3$ is $10$. So answer is $10$. It turns out the answer is: $$k+⌊\tfrac{k-1}{n-1}⌋$$

I want the mathematical intuition behind this formula.

Answer 1

==== old answer ===

Assume the answer is $M$.

Then there are $k$ numbers less than or equal to $M$ that are not divisible by $n$.

So $k = f(M)$ where $f(M)$ is the function that tells you how many number less than or equal to $M$ are not divisible by $n$.

So if we can "undo" $f(M)$ to get $f^{-1}(k) = M$ we can solve for $M$.

Now there is a unique number $m$ so that $M = m*n + r$ where $0\le r < n$. That's just division.

In other words, $m*n \le M < (m+1)n$. But as $n$ doesn't divide $M$ we have.

$m*n < M < (m+1)n$.

And the numbers $n, 2n, 3n,.....,mn$ are all divisible by $n$. And all the rest of the numbers are not.

So there are $M- m = k$ numbers that are not divisible $n$ that are equal or less than $M$.

So what is $m$?

So $mn < M < (m+1)n$ so $m < \frac Mn < m+1$ so $m = \lfloor \frac Mn \rfloor$.

And we have $M - \lfloor \frac Mn \rfloor = k$

So now we must solve for $M$ in terms of $n$ and $k$.

Let's go.....

$M - \lfloor \frac Mn \rfloor = k$

$\lfloor \frac Mn \rfloor = M-k$

$M-k < \frac Mn < M-k +1$ (We know $n\not \mid M$ so we have strict inequalities)

$Mn-kn < M < Mn -kn + n$

$-kn < M-Mn < -kn +n$

$kn- n < Mn-M < kn$

$(k-1)\frac n{n-1} < M < k\frac n{n-1}$

Now $\frac n{n-1} < 1$ so there is (apparently) exactly one integer, $M$ so that $(k-1)\frac n{n-1} < M$ and that $k\frac n{n-1} > M$.

$k\frac n{n-1} = k\frac {(n-1)+1}{n-1} = k(1 + \frac 1{n-1})= k + \frac k{n-1}$

And $(k-1)\frac n{n-1} = (k-1)(1 + \frac 1{n-1}) = k-1 + \frac {k-1}{n-1}=k + \frac{k-n}{n-1}$.

So we have the only integer $M$ so that $k + \frac {k-n}{n-1} < M < k + \frac {k}{n-1}$.

If $\frac k{n-1}$ is an integer then $k+\frac k{n-1}$ is too big.

But if $h \le k-1$ and $\frac h{n-1}$ is an integer then $M \ge k + \frac h{n-1}$.

So $M$ is the $k + $ the largest integer less than or equal to $\frac {k-1}{n-1}$

So $M = k + \lfloor \frac {k-1}{n-1} \rfloor$.

=====

Actually that last bit was pretty confusing.

Go back to $(k-1)\frac n{n-1} < M < k\frac n{n-1}$

Now lets jump ahead and consider $k + \lfloor \frac {k-1}{n-1}\rfloor$

Let $h = \lfloor \frac {k-1}{n-1}\rfloor$.

So $h\le \frac {k-1}{n-1}< \frac {k}{n-1}$

And $\frac {k-1}{n-1} - 1=\frac {k-n}{n-1} < h$.

So $k + \frac {k-n}{n-1}< k + \lfloor \frac {k-1}{n-1}\rfloor <k+\frac {k}{n-1}$

But also $(k-1)\frac n{n-1} < M < k\frac n{n-1}$.

But there is at most one integer in that range. So as both $M$ and $k + \lfloor \frac {k-1}{n-1}\rfloor$ are both integers, they must be equal.

Answer 2

We need the $k^{th}$ integer not divisible by $n$. At first, we list all the integers not divisible by $n$. We don't know the values of these integers yet.

$$1^{st}, 2^{nd}, 3^{rd}, ..., k^{th}$$

This list omits the integers divisible by $n$. We need to know exactly how many such integers are omitted to find the value of the $k^{th}$ integer.

Exactly one integer (which is divisible by n) is omitted after $(n-1)$ integers. So, we need to know how many groups of $(n-1)$ integers do we encounter before reaching the $k^{th}$ integer. In other words, we will try to count the number of blocks of $(n-1)$ integers up till the $(k-1)^{th}$ non-divisible integer. And, that number is $\lfloor \frac{k-1}{n-1} \rfloor$.

The point of confusion might be the appearance of $(k-1)$. Remember, we need to find the number of $(n-1)$ integer blocks before we reach the $k^{th}$ integer. Examples might shed some light upon this.

Take $k=6$ and $n=3$ first. (I'll be omitting the positional identifiers, such as 'st, 'nd, 'th, etc.)

$$1,2,|,3,4,|,5,6,|$$

The pipe symbols express the position of the omitted integers. If we take $\lfloor \frac{k}{n-1} \rfloor$, we count the integer after the $6^{th}$ as well, which we don't want. Hence, we take $\lfloor \frac{k-1}{n-1} \rfloor$, which counts the missing integers before the $6^{th}$.

For the next example, consider $k=6$ and $n=2$. The missing integers will be placed like this.

$$1,|,2,|,3,|,4,|,5,|,6,|$$

Again, to count the missing integers before the $6^{th}$, we are gonna check how many groups of $(2-1)$ we can make up till the $5^{th}$. Hence $\lfloor \frac{6-1}{2-1} \rfloor$.

Answer 3

Firstly, we can think about how multiples of $n$ appear in a sequence. For example, when $n=4$: $$1,2,3,[4],5,6,7,[8],9,10, ...$$ Secondly, we are asked to determine the $k^{th}$ position in the sequence above, "skipping" multiples of $n$. For example when $k=5$, using the same sequence above: $$1,2,3,[4],5, \langle 6 \rangle ,7,[8],9,10, ...$$ The number $ \langle 6 \rangle $ comes in this natural $6th$ position, but because there's $1$ multiple of $4$ before it, its $k^{th}$ position is deducted by $1$, thus $k^{th}$ of the position $5$ equals $6$.

We can now generalise this counting of multiples by organising them into blocks. This is the spatial reasoning involved in the intuition for the solution: $$\underline{[1,2,3]},4,\underline{[5,6,7]},8,\underline{[9,10,} ...$$ From the above, clearly, we're counting how many blocks of $3$ (that is $n-1$) precede the numbers that are multiples of $n$, until the $k^{th}$ provided: $$\lfloor{\frac{k}{n-1}}\rfloor$$ The above will give us how many blocks of numbers, therefore how many multiples, we can "offset" our desired ${k^{th}}$ number, so: $$k+\lfloor{\frac{k}{n-1}}\rfloor$$ This sort of works, let's see: $$ \begin{aligned} k=5, n=4\\ 5+\lfloor{\frac{5}{4-1}}\rfloor\\ = 5+\lfloor{\frac{5}{3}}\rfloor\\ = \langle 6 \rangle\\ \end{aligned} $$ The problem seems to be if $k$ is a multiple of $n-1$ because we will be counting an extra multiple, for example $k=6$, with $n-1 = 3$, we'll have: $$ k=6, n=4\\ 6+\lfloor{\frac{6}{4-1}}\rfloor\\ = 6+\lfloor{\frac{6}{3}}\rfloor\\ = 8 \;\; \text{ WRONG! Correct will be $7$} $$ Ok, when we hit a block size that divides $k$, we'll have to deduct $1$, since we don't want to count that extra block, so we have: $$ answer\bigl(k,n \bigr) = \begin{cases} k+\lfloor{\cfrac{k}{n-1}}\rfloor - 1 & \text{, if $n-1 \mid k$}\\ k+\lfloor{\cfrac{k}{n-1}}\rfloor & \text{, if $n-1 \nmid k$ } \end{cases} $$ This could be the final answer to the problem. It's also $O(1)$ and easy to deconstruct. But we could go further, due to the identities: $$ \begin{matrix} \lfloor{\cfrac{m+1}{n}}\rfloor = \lfloor{\cfrac{m}{n}}\rfloor + 1 & \text{, if $n \mid m+1$} & (\alpha)\\ \lfloor{\cfrac{m+1}{n}}\rfloor = \lfloor{\cfrac{m}{n}}\rfloor & \text{, if $n \nmid m+1$} & (\beta) \end{matrix} $$ The identities above are easier to reason about, if we prove our intuition using same numbers from our cases above, like so: $$ \lfloor{\cfrac{5+1}{4-1}}\rfloor = \lfloor{\cfrac{5}{3}}\rfloor + 1 \text{, because $4-1 \mid 5+1$}\\ \lfloor{\cfrac{6+1}{4-1}}\rfloor = \lfloor{\cfrac{6}{3}}\rfloor \text{, because $4-1 \nmid 6+1$} $$ Or: $$ \lfloor{\cfrac{6}{3}}\rfloor = \lfloor{\cfrac{5}{3}}\rfloor + 1 \text{, because 3 | 6}\\ \lfloor{\cfrac{7}{3}}\rfloor = \lfloor{\cfrac{6}{3}}\rfloor \text{, because $3 \nmid 7$} $$ Or: $$ \begin{matrix} \lfloor{\cfrac{k}{n-1}}\rfloor = \lfloor{\cfrac{k-1}{n-1}}\rfloor + 1 & \text{, if $n-1 \mid k$} & (\alpha)\\ \lfloor{\cfrac{k}{n-1}}\rfloor = \lfloor{\cfrac{k-1}{n-1}}\rfloor & \text{, if $n-1 \nmid k$} & (\beta) \end{matrix} $$ That's where our $k-1$ comes from. So: $$ k+\lfloor{\frac{k}{n-1}}\rfloor - 1 \text{, if $n-1 \mid k$}\\ \stackrel{\text{from $(\alpha)$}}{=} k+\lfloor{\frac{k-1}{n-1}}\rfloor + 1 - 1\\ = k+\lfloor{\frac{k-1}{n-1}}\rfloor $$ And: $$ k+\lfloor{\frac{k}{n-1}}\rfloor \text{, if $n-1 \nmid k$}\\ \stackrel{\text{from $(\beta)$}}{=} k+\lfloor{\frac{k-1}{n-1}}\rfloor $$ We can combine the two answers now, since both will apply regardless of whether $n-1$ divides $k$ or not: $$ k+\biggl\lfloor{\frac{k-1}{n-1}}\biggr\rfloor $$ Q.E.D.