I was asked this question long time ago. Having a function $rand2()$ (in any computer language, "rand" means random) which returns $0$ or $1$ (two values only) with a uniform distribution, i.e. $$P(rand2()=0)=P(rand2()=1)$$ compute the function $rand5()$ which returns $0,1,2,3$ or $4$ with uniform distribution, i.e. $$P(rand5()=0)=P(rand5()=1)=P(rand5()=2)=P(rand5()=3)=P(rand5()=4)$$
I have an answer: use voting to promote each $k \in \{0,1,2,3,4\} = L_0$ ($L$ means level) to the next level $L_1$, depending on whether $rand2()$ returns $0$ (not promoted) or $1$ (promoted). If none is promoted, start again, until at least one such $k$ is promoted. At the end of this iteration we obtain $L_1 \subseteq L_0$. Do the same with $L_1$ to obtain $L_2 \subseteq L_1 \subseteq L_0$. And so on, until we reach some level $L_n$ containing only one element. That element is returned as the value for $rand5()$.
This seem to have a uniform distribution, because every element is given an equal chance. But I have a problem with the maths for proving this.
E.g. $k\in L_0$ being promoted to level $p$ means $$P(k\in L_p)=\frac{1}{2^p}$$
$k\in L_0$ not reaching level $p$ means $$P(k\notin L_p)=1-\frac{1}{2^p}$$
$k\in L_0$ "wins" at level $p$ means $$P(L_p=\{k\})=\frac{1}{2^p}\cdot \left ( 1-\frac{1}{2^p} \right )^4$$
$k\in L_0$ "wins" (at any level $>0$) means $$P(rand5()=k)=\sum_{p=1}^{\infty}P(L_p=\{k\})$$ which, using MathWolfram, happens to be equal to $0.289400...$, not the expected $0.2$. I believe I missed the "If none is promoted, start again, until at least one such $k$ is promoted" part in my calculations. But I am a bit lost trying to inject it into the final calculations.
Any help is much appreciated. Or even a better and more efficient algorithm, with less calculations involved.