2048 is a game of making powers of two. Each turn a number 2 or 4 is generated at a randomly chosen tile. We merge two of the same number to make a twice as larger one. For example, merging two 2s makes 4, and merging two 4s makes 8, and so on. See, e.g. Wikipedia for more in detail about the game, or it may be easier to play a few games to understand the rule (freely available as a browser game and an app).
The scoring rule of the game is simple: When we make a number X, we earn score X. In this article, we consider the following math question:
Question. How many scores in total do you earn by making a number 2ⁿ? For simplicity, assume that only 2s are randomly generated.
Examples. Let aₙ denote the total score for making a 2ⁿ.
- You receive no score for 2 (= 2¹). So a₁ = 0.
- You receive score 4 for making a 4 = 2², so a₂ = 4. Note that we assume 4s are not randomly generated.
- To make an 8 = 2³, you first need to make two 4s, from which you earn 2 × 4 = 8. Then you receive 8 by making them into an 8. So a₃ = 2 × 4 + 8 = 16.
- For 16 = 2⁴, you earn 2 × 16 = 32 for making two 8s and 16 for making the number. So, a₄ = 2 × 16 + 16 = 48.
Turning into a math problem
By the examples above, the total score aₙ follows the following recurrent relation:
aₙ = 2 aₙ-₁ + 2ⁿ
for n > 1, with the initial condition a₁ = 0.
This form of recurrent relation is new to me. So I put this into the computer first.
Asking Excel
I typed in the formula above to Excel and computed the following.
+----+-------+--------+
| n | 2^n | a_n |
+----+-------+--------+
| 1 | 2 | 0 |
| 2 | 4 | 4 |
| 3 | 8 | 16 |
| 4 | 16 | 48 |
| 5 | 32 | 128 |
| 6 | 64 | 320 |
| 7 | 128 | 768 |
| 8 | 256 | 1792 |
| 9 | 512 | 4096 |
| 10 | 1024 | 9216 |
| 11 | 2048 | 20480 |
| 12 | 4096 | 45056 |
| 13 | 8192 | 98304 |
| 14 | 16384 | 212992 |
| 15 | 32768 | 458752 |
| 16 | 65536 | 983040 |
+----+-------+--------+We see that the score blows up very quickly. Calculating is easy with the help of spreadsheet software. But can we derive a formula for aₙ?
Solution
Consider:
aₙ = 2 aₙ-₁ + 2ⁿ
Divide both sides by 2ⁿ. Then, we obtain
aₙ / 2ⁿ = aₙ-₁ / 2ⁿ⁻¹ + 1
Define bₙ = aₙ / 2ⁿ, then equation above can be written as
bₙ = bₙ-₁ + 1
By the iterative substitution, we obtain
bₙ = bₙ-₁ + 1 = bₙ-₂ + 2 = bₙ-₃ + 3 = … = b₁ + (n−1)
Noting that b₁ = a₁ / 2 = 0, we have
bₙ = n−1
Substituting bₙ = aₙ / 2ⁿ and arranging, we get
aₙ = (n−1) 2ⁿ
We can confirm that this formula yields a₁ = 0, a₂ = 4, a₃ = 16, … as desired. And more generally for all n on Excel:
+----+-------+--------+-------------+
| n | 2^n | a_n | (n-1) * 2^n |
+----+-------+--------+-------------+
| 1 | 2 | 0 | 0 |
| 2 | 4 | 4 | 4 |
| 3 | 8 | 16 | 16 |
| 4 | 16 | 48 | 48 |
| 5 | 32 | 128 | 128 |
| 6 | 64 | 320 | 320 |
| 7 | 128 | 768 | 768 |
| 8 | 256 | 1792 | 1792 |
| 9 | 512 | 4096 | 4096 |
| 10 | 1024 | 9216 | 9216 |
| 11 | 2048 | 20480 | 20480 |
| 12 | 4096 | 45056 | 45056 |
| 13 | 8192 | 98304 | 98304 |
| 14 | 16384 | 212992 | 212992 |
| 15 | 32768 | 458752 | 458752 |
| 16 | 65536 | 983040 | 983040 |
+----+-------+--------+-------------+Remarks
When you play the game, you will notice that aₙ we have calculated is roughly equal to the score right after you make a 2ⁿ. This is only “roughly” equal because:
- There are remainder numbers (typically small) that were not used to make the 2ⁿ, leading to more score.
- Some 4s are randomly generated, for which we earn no score, leading to less score.
In my experience, the second factor outweighs the first, so the total score tends to be slightly smaller than aₙ.
Writing Tools
- Tex to Unicode. Chrome extension that renders math expressions while typing.
- ASCII Table Generator. Online converter of tables into formatted ASCII table.