I am given a uniform integer random number generator $\sim U_3(1,3)$ (inclusive). I would like to generate integers $\sim U_5(1,5)$ (inclusive) using $U_3$. What is the best way to do this?
This simplest approach I can think of is to sample twice from $U_3$ and then use rejection sampling. i.e., sampling twice from $U_3$ gives us 9 possible combinations. We can assign the first 5 combinations to 1,2,3,4,5, and reject the last 4 combinations.
This approach expects to sample from $U_3$ $\frac{9}{5} * 2 = 18/5 = 3.6$ times.
Another approach could be to sample three times from $U_3$. This gives us a sample space of $27$ possible combinations. We can make use of $25$ of these combinations and reject the last 2. This approach expects to use $U_3$ $\frac{27}{25} * 3.24$ times. But this approach would be a little more tedious to write out since we have a lot more combinations than the first, but the expected number of sampling from $U_3$ is better than the first.
Are there other, perhaps better, approaches to doing this?
Your calculations are correct. The more efficient rejection sampling scheme is to generate three $U_3$ variables, say $U_{3,0}, U_{3,1}, U_{3,2}$ and compute $$S_3 = \sum_{i=0}^2 3^i (U_{3,i} - 1).$$ If $S_3 > 25$, which happens with probability $2/27$, we generate another set (i.e., reject); otherwise, we compute $\lceil S_3/5\rceil$ and this will be distributed as $U_5$. I don't think this is too computationally expensive to implement compared to the two-variable case. For instance, if you generate the sample $$(3,1,2),$$ then you can compute $$(3,1,2) \cdot (9,3,1) - 13 = 19,$$ or $$(2,0,1) \cdot (9,3,1) = 19;$$ both are equivalent. Then since $19 \le 25$, we compute $\lceil 19/5 \rceil = 4$.