# 2048 and algebra (Part 8)

In this series of posts, I consider how algebra can be used to answer a question about the 2048 game: From looking at a screenshot of the final board, can I figure out how many moves were needed to reach the final board? Can I calculate how many new 2-tiles and 4-tiles were introduced to the board throughout the course of this game? In this post, we consider the event horizon of 2048, which I reached after about four weeks of intermittent doodling:

In yesterday’s post, we developed a system of two equations in two unknowns to solve for $t$ and $f$, the number of 2-tiles and 4-tiles (respectively) that appeared throughout the course of the game:

$2t + 4f = \displaystyle \sum_{n=2}^{17} 2^n$.

$2t + \displaystyle \sum_{n=1}^{15} n \cdot 2^{n+2} = 3,867,072$

In this post and tomorrow’s post, I consider how the two sums in the above equations can be obtained without directly adding the terms.

In yesterday’s post, we showed that the formula for the sum of a finite geometric series can be used to calculate the first sum:

$\displaystyle \sum_{n=2}^{17} 2^n = \displaystyle \frac{4(1-2^{16})}{1-2} = 4(2^{15} - 1) = 262,140$

Let’s now consider the second (and more complicated) sum, which can be written as

$2^3 + 2 \cdot 2^4 + 3 \cdot 2^5 + \cdot + 15 \cdot 2^{17}$

For reasons that will become clear shortly, this sum can be written in expanded form as

$2^3$

$+ 2^4 + 2^4$

$+ 2^5 + 2^5 + 2^5$

$\vdots$

$+ 2^{17} + 2^{17} + 2^{17} + \dots + 2^{17}$

Let’s now rearrange the terms of this sum. We will do this by adding along the diagonals instead of along the rows. In this way, the above sum can be rearranged as

$2^3 + 2^4 + 2^5 + \dots + 2^{17}$

$+ 2^4 + 2^5 + \dots + 2^{17}$

$+ 2^5 + \dots + 2^{17}$

$\vdots$

$+ 2^{17}$

Each of these new rows (or the original diagonals) is a geometric series and can be calculated using the formula:

$2^3 + 2^4 + 2^5 + \dots + 2^{17} = \displaystyle \frac{2^3 (1-2^{15})}{1-2} = 2^{18} - 2^3$

$2^4 + 2^5 + \dots + 2^{17} = \displaystyle \frac{2^4 (1-2^{14})}{1-2} = 2^{18} - 2^4$

$2^5 + \dots + 2^{17} = \displaystyle \frac{2^5 (1-2^{13})}{1-2} = 2^{18} - 2^5$

$\vdots$

$2^{17} = (2-1) \cdot 2^{17} = 2^{18} - 2^{17}$

So, thus far in the calculation, we have established that

$\displaystyle \sum_{n=1}^{15} n \cdot 2^{n+2} = \displaystyle \sum_{n=3}^{17} \left( 2^{18} - 2^n \right)$.

Simplifying,

$\displaystyle \sum_{n=1}^{15} n \cdot 2^{n+2}=\displaystyle \sum_{n=3}^{17} 2^{18} - \sum_{n=3}^{17} 2^n$

The first sum on the right is the sum of a constant being added to itself 15 times:

$\displaystyle \sum_{n=3}^{17} 2^{18} = 15 \times 2^{18}$

The second sum on the right is yet another geometric series. Indeed, it’s the same geometric  series from the first diagonal above:

$\sum_{n=3}^{17} 2^n = \displaystyle \frac{2^3 (1-2^{15})}{1-2} = 2^{18} - 2^3$

Therefore,

$\displaystyle \sum_{n=1}^{15} n \cdot 2^{n+2} = 15 \times 2^{18} - \left(2^{18} - 2^3 \right)$

$\displaystyle \sum_{n=1}^{15} n \cdot 2^{n+2} = 14 \times 2^{18} + 2^3$

$\displaystyle \sum_{n=1}^{15} n \cdot 2^{n+2} = 3,670,024$

Not surprisingly, this matches the sum that was found via direct addition.