How to find k'th integer not divisible by n? 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.
 A: 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$.
A: ==== 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.
A: 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.
