Use a k-sided die to generate integer in range [0 n] with the least number of throws. Given a fair $k$-sided die, with $k < n$, what is a generic method that allows me to generate a number in the range $[0...n]$ with the same probability and with the least amount of throws?
I have found many answer to similar specific questions, but I could not figure out a general method to achieve this.
 A: It cannot be done unless every prime divisor of $n+1$ is a prime divisor of $k$. 
That's because in $m$ tosses, there are $k^m$ possible outcomes, and an equal number of them must go to each of the $n+1$ values, $0,1,2,...,n$, which means that $k^m$ must be divisible by $n+1$. That's possible if and only if every prime divisor of $n+1$ is a divisor of $k$.
It is certainly possible to do it in $m$ tosses when $n+1$ is a divisor $k^m$. Take most intuitive algorithm is to take the $m$ numbers, $a_1,...,a_m$ from $0$ to $k-1$ and write them as a base $k$ number:
$$a_1+a_2k+a_3k^3+...+a_mk^{m-1}$$
then divide this number by $n+1$ and take the remainder.
A: Assuming that the numbers on the sides of the die are $\{1,2,3,\cdots,k\}$
First we will subtract one from every side so it becomes $\{0,1,2,\cdots,k-1\}$
Now we will throw the die $\lfloor \log_{k} (\frac{n}{k-1}) \rfloor + 1$ times, each time we will multiply its side subtract one with $k^{\lfloor \log_{k} (\frac{n}{k-1}) \rfloor + 1-j}$ where $j$ is from $0$ to$\lfloor \log_{k} (\frac{n}{k-1}) \rfloor + 1$,and then sum all the results together, so by this way we can generate any number between $0$ and $k^{j+1}-1$ inclusive (base $k$ representation).
note : if before throwing the die the sum is less than $n$ and after throwing the side the sum is bigger than $n$ then we will not include it and throw it again(its guaranteed to produces numbers between $[0,n]$ with fair (equal probability to each number), the only down side is that you sometimes need to throw more than once to reach a valid side.
Example : for given $k=3$ and $n=17$ so the sides of the die are numerated from $0$ to $2$, also $\lfloor \log_3 \frac{17}{2} \rfloor +1 =2$ ,so we start by throwing the die and it land on $2$ but since $2*3^2$ is bigger than $17$ so we throw it again and landed on $0$ now the sum is $0*3^2$ so its 0 which is less than 17(good) now we throw it again and we land at $1$ so its equal to $1*3^1$ which is equal to 3 and its less than 17 and finally we throw it again and it land on $2$ so its $2*3^0$ and the sum is $3+2=5$ which is less than 17.
so we generate $5$ randomly with $3$ sided die and it must be less or equal to 17.
to sum it up (all that i did is representing $n$ in base $k$) so if you don't understand the answer, read about base $b$ representation in Wikipedia.
also i would like to see someone who could overcome the re-throwing problem in my solution!
i hope you see what you are looking for. 
