8

Part of 2012 BMT Spring

Problems(2)

Spring Round (2012) #8

Source:

You are tossing an unbiased coin. The last

28

consecutive ﬂips have all resulted in heads. Let

x

be the expected number of additional tosses you must make before you get

60

consecutive heads. Find the sum of all distinct prime factors in

x

modular arithmeticEulerprobabilityexpected value

2012 BMT Team 8

Source:

\phi

be the Euler totient function. Let

\phi^k (n) = (\underbrace{\phi \circ ... \circ \phi}_{k})(n)

\phi

composed with itself

k

times. Define \theta (n) = min \{k \in N | \phi^k (n)=1 \} . For example,

\phi^1 (13) = \phi(13) = 12

\phi^2 (13) = \phi (\phi (13)) = 4

\phi^3 (13) = \phi(\phi(\phi(13))) = 2

\phi^4 (13) = \phi(\phi(\phi(\phi(13)))) = 1

\theta (13) = 4

f(r) = \theta (13^r)

f(2012)