Bon Pint

The nerdier regulars at the Bon Pint pub enjoy a peculiar number game. They start with an integer \(n\) and expand it in powers of 2. Then, they expand all the exponents in powers of two, and so on, until \(n\) is written with just 1s and 2s. For example, \(9 = 2^3 + 1 = 2^{(2^1 + 1)} + 1\). They then make a new number by replacing each 2 with 3 and subtracting 1 from the result, carrying terms (like grade school math subtraction, see example below) to ensure all the coefficients in the base 3 representation are positive. Next, they replace 3 with 4 and subtract 1, and so on. They keep going until the pub closes or the sequence stops, whichever comes first. How often do they stop? If they stop, how long do they play?

To get you started, here’s the game for \(n=2,3\) and the initial terms for \(n=4\).

• When \(n=2\), the game stops after 3 steps: \(2^1\rightarrow 3^1-1=2 \rightarrow 1 \rightarrow 0\).
• When \(n=3\), it stops after 5 steps: \(2^1+1\rightarrow 3^1+1-1=3^1 \rightarrow 4^1-1=3 \rightarrow 2 \rightarrow 1 \rightarrow 0\).
• When \(n=4\), the game starts: \(2^2\rightarrow 3^3-1=2\times 3^2 + 2\times 3 + 2 = 26\), which illustrates carrying (twice) to ensure all coefficients are positive. The sequence continues, \(26 \rightarrow 2\times 4^2 + 2\times 4 + 1=41 \rightarrow 60 \rightarrow 83 \rightarrow 109\rightarrow\dots\).

First, decide the outcome for \(n=4\). Then try to generalize. Show your work for partial credit.