Two heads are better than one
Problem 624
An unbiased coin is tossed repeatedly until two consecutive heads are obtained. Suppose these occur on the th and th toss.
Let be the probability that is divisible by . For example, the outcomes HH, HTHH, and THTTHH all count towards , but THH and HTTHH do not.
Let be the probability that is divisible by . For example, the outcomes HH, HTHH, and THTTHH all count towards , but THH and HTTHH do not.
You are given that and . Indeed, it can be shown that is always a rational number.
For a prime and a fully reduced fraction , define to be the smallest positive for which .
For example , because and 66 is the smallest positive such number.
Similarly .
For example , because and 66 is the smallest positive such number.
Similarly .
Find .