Unbiased random number generator

we have a six-sided dice numbered from 1 to 6, and each has the probability $p =\frac{1}{6}$. My task is to create a unbiased method to generate a random number from 1 to 10 using the given dice.
I am aware that the method should maps the following set $$ \{1,\dots 6\}^k\mapsto \{1,\dots, 10\}$$, with $k$ is the number of time we throw the dice. For sure not the 36 elements will be mapped into the set containing 1 to 10. What i mean, the method will use a while loop and only stops if a certain tuple is found. My task then is the find those tuples and prove each thoese 10 tuples has the probaitly of $\frac{1}{10}.$
I think $k$ should be 2 in this case , but then i am not quite sure how to extract the 10 elements from 36 elements ($6^k$,with $k=2$) and have a probability of $p'=\frac{1}{10}$.
can we maybe also generalize that for$ n$ elements ?

$$ \{1,\dots 6\}^k\mapsto \{1,\dots, n\} $$
I will appreciate any good ideas.

Here is the algorithm for $n=10$.

• Throw the dice twice to get $(x,y)$.

• Compute $r=x + 6(y-1)$. If $r\le10$, return $r$ and stop.

• If we have reached here, go back to step 1.

Here is the algorithm for general $n$.

• Compute $n=\lceil \log_6k\rceil$.

• Throw the dice $n$ times to get $(x_1, x_2, \cdots, x_n)$.

• Compute $r=x_1+6(x_2-1)+6^2(x_3-1)+\cdots+6^{n-1}(x_n-1)$. If $r\le k$, return $r$ and stop.

• If we have reached here, go back to step 2.

There are many variations, of course.

For example, in step 2 for $n=10$, we can return $r=10 - (x + 6(y-1))\%10$ and stop when $x+6(y-1)\le30$ instead. This will reduce the chance to go to step 2. Here % is the remainder operator.

For example, here is gnasher729's algorithm for $n=10$. Throw a dice until we get a number $x\not=6$. Throw the dice once more to get another number $y$. Return ((x - 1) * 6 + (y - 1))%10+1$.

(Exercise 1.) (One minute or less) Devise an algorithm for $n=3$.

(Exercise 2.) Devise an algorithm for $n=7$. Try making its expected number of rolls as small as possible.

(Exercise 3.) Prove that the expected number of rolls in gnasher729's algorithm is the minimum among all algorithms.

(Exercise 4.) Given any $n>1$, devise an algorithm with the least expected number of rolls.

StackExchange Computer Science Q#103695, answer score: 4