Hello codeforces! A while back I presented myself with a challenge to build a random function from only random bits. However, in the process of doing so, I realized that not only was this much more difficult than I expected, I ended up wondering whether it is possible at all. So here's what I did and the challenges I faced before asking you for a solution:

Creating 1/powers of 2 is trivial, since flipping n coins can create 2^n random possibilities.

Similarly, the same thing would be possible with dice, for example flipping two die and then multiplying one dice by 6 and adding them together can yield a 1/36 chance.

This seems to be limited to the factors given though, a dice can create 1/12 or 1/18 as well, using mod.

I don't want to have to flip potentially infinite coins. So, I can't get a 1/8 chance and then reroll on an 8 to get a 1/7 chance.

I first attempted to use different flips of powers of two using the binary representation. For example, for a 1/7 chance I thought to flip 4, then 2, then 1 coin. However, it seems this distribution is not even, you have to play plinko to get 0 or 7.

So my next idea was to create a super large value from say 1000 coins and then divide to the value. Effectively a 1/7 chance but, not perfect either way. This just minimizes rerolls, since it minimzies the ratio when creating a 1/n chance since as a value k gets bigger 2^k % n is smaller relative to 2^k.

Apologies if this is a solved problem, or if this is a well known unsolved problem. This was on my mind for a while now.