<s>[INST] 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.
 [/INST] 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.
</s>