Skip to main content.

Second 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).

Using the above recurrence relation, calculate the first few values of E(n).  Make, and prove, a conjecture about the value of E(k+1) − E(k).