Expecting Perfection

Let $E_{k,j}$ be the expected number of tosses of the coin to get $k$ tails in a row, given that we already have a run of $j$ heads. Then $E_{k,k} = 0$ while $E_{k,j} \; =\; \tfrac12(1 + E_{k,0}) + \tfrac12(1 + E_{k,j+1}) \hspace{2cm} 0 \le j \le k-1$ Thus $\begin{aligned} 2E_{k,j} & = \; 2 + E_{k,0} + E_{k,j+1} \\ \frac{E_{k,j}}{2^j} & = \; \frac{2 + E_{k,0}}{2^{j+1}} + \frac{E_{k,j+1}}{2^{j+1}} \\ E_{k,0} - \frac{E_{k,j}}{2^j} & = \; \sum_{r=0}^{j-1}\left(\frac{E_{k,r}}{2^r} - \frac{E_{k,r+1}}{2^{r+1}}\right) \; = \; \sum_{r=0}^{j-1}\frac{2 + E_{k,0}}{2^{r+1}} \; = \; \big(2 + E_{k,0}\big)(1 - 2^{-j}) \end{aligned}$ with the last identity being valid for $0 \le j \le k$ . Thus, putting $j=k$ , we obtain $\begin{aligned} E_{k,0} & = \; \big(2 + E_{k,0}\big)(1 - 2^{-k}) \\ E_{k,0} & = \; 2(2^k - 1) \end{aligned}$ and $E_{k,0}$ is the expected number of tosses to get a sequence of $k$ tails in a row. We want $E_{k,0}$ to be a perfect number, which occurs when $k=\boxed{2}$ , since $E_{2,0} = 6$ . Since the even perfect numbers are of the form $2^{p-1}(2^p-1)$ where $p$ and $2^p-1$ are both prime, it is clear that $k=2$ is the only solution.

Let $E$ be the expected number of flips to get $k$ tails in a row. If your first flip in a new sequence is tails, you have to start over for an added expected value of $1 + E$ , which will happen $\frac{1}{2}$ of the time. If your first flip in a new sequence is heads and your second flip is tails, you have to start over for an added expected value of $2 + E$ , which will happen $\frac{1}{4}$ of the time. Continue with this reasoning until your first $k - 2$ flips in a new sequence are heads and your second flip is tails, then you have to start over for an added expected value of $k - 1 + E$ , which will happen $\frac{1}{2^{k - 1}}$ of the time. And if your first $k - 1$ flips in a new sequence is tails, then there is a $\frac{1}{2}$ chance of getting the $k$ tails in a row and a $\frac{1}{2}$ chance of having to start over, for an added expected number of $\frac{1}{2}k + \frac{1}{2}(k + E)$ , which will happen $\frac{1}{2^{k - 1}}$ of the time. Therefore,

$E = \frac{1}{2^1}(1 + E) + \frac{1}{2^2}(2 + E) + ... + \frac{1}{2^{k - 1}}(k - 1 + E) + \frac{1}{2^{k - 1}}(\frac{1}{2}k + \frac{1}{2}(k + E))$

which solves to

$E = 2^{k - 1} \cdot 1 + 2^{k - 2} \cdot 2 + ... + 2^1 \cdot (k - 1) + 2k$

This can be shown inductively to be

$E = 2(2^k - 1)$

$E$ is necessarily even, and all even perfect numbers are in the form of $2^{p - 1}(2^p - 1)$ . By examining each equation, we can conclude that $p - 1 = 1$ and $p = k$ , which solves to $p = k = \boxed{2}$ (for an perfect expected value of $6$ ).