Skip to main content.

First hint to puzzle 67: Random number generator

Let E(n) be the expected value of the number of iterations by which the generator first outputs the number 1, when the initial input parameter is equal to n.

We have E(1) = 1.  Show that, for n > 1, E(n) = 1 + (E(1) + ... + E(n−1)) / (n − 1).