Solution 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.

Establishing a recurrence relation

Clearly E(1) = 1.

For n > 1, E(n)	= [E(1) + (1 + E(2)) + ... + (1 + E(n))] / n. (Consider n equally likely outcomes, following the first iteration.)
	= (n − 1 + E(1) + E(2) + ... + E(n)) / n.

(Notice that we have implicitly assumed that E(n) is finite, which is something that, a priori, we do not necessarily know.)

Multiplying by n and rearranging, we have (n − 1)E(n) = (n − 1) + E(1) + ... + E(n−1).
Therefore E(n) = 1 + (E(1) + ... + E(n−1)) / (n − 1).

Proving a harmonic sum conjecture

Though useful, this recurrence relation does not provide an easy means for calculating or approximating E(n), for large values of n.
However, calculating the first few values: E(1) = 1, E(2) = 2, E(3) = 5/2, E(4) = 17/6, E(5) = 37/12; we may conjecture that E(k+1) − E(k) = 1/k.

To prove this conjecture, consider

E(k+1) − E(k)	= [E(1) + ... + E(k)] / k − [E(1) + ... + E(k−1)] / (k − 1).
	= E(k) / k − [E(1) + ... + E(k−1)] / k(k − 1).
	= E(k) / k − [E(k) − 1] / k.
	= 1/k.

We can now derive an expression for E(n), for n > 1, using the following telescoping sum:

E(1) = 1
E(2) − E(1) = 1/1
E(3) − E(2) = 1/2
...
E(n) − E(n−1) = 1/(n−1)

Adding, we have E(n) = 1 + (1/1 + ... + 1/(n−1)).

Harmonic sum approximation

Now we can obtain a very accurate approximation for E(10¹⁰⁰).

It is known that, for large n, the harmonic sum, 1/1 + ... + 1/n, is asymptotically equal to ln n + Y + 1/2n, where Y = 0.5772156649... is the Euler-Mascheroni Constant.

Setting n = 10¹⁰⁰, we obtain E(10¹⁰⁰) 1 + (100 ln 10) + Y 231.8357.

Therefore, E(10¹⁰⁰), the expected value of the number of iterations by which the generator first outputs the number 1, equals 232, to the nearest integer.

Source: Original. See also Puzzle 33. Harmonic Sum.