It’s December, so it’s time for a lot of things, including Advent of Code. I will not be able to be as competitive as I was last year, and already lost a lot of points to a really silly mistake on day 1, but I’ll be playing when I can and golfing the problems when I have time (so far: 7 + 14 bytes).
As one might expect, Day 1 is not too complex, but the second part can be analyzed to some mathematical depth and was discussed a bit on Reddit; plus, it occurred to me recently that I set up KaTeX on my blog but never used it, so I was looking for an excuse to write some equations anyway.
The problem statement for part 2, in brief: We are tasked with calculating the total mass of fuel required to launch a rocket module of a given mass. For something of mass \(m\), one can compute the directly required mass of fuel by dividing \(m\) by 3, rounding down, and subtracting 2; if the result is negative, it is taken to be 0 instead. However, the directly required fuel also requires fuel itself, calculated from its own mass by the same procedure, and that required fuel requires fuel based on its own mass, and so on until you reach fuel with 0 requirement.
This is easy to program by just following instructions, but one might wonder whether there is a closed form. Not exactly, but we can certainly learn more about the behavior of the answer in terms of the module mass.
Let \(x_0 := m\) be the mass of a given module, and for \(i \geq 0\) let \(x_{i+1}\) be the fuel directly required for something of mass \(x_i\). We are given that \[\tag{1} x_{i+1} = \max\left(\left\lfloor\frac{x_i}{3}\right\rfloor - 2, 0\right).\] Then, given \(m\), we want to calculate the total required fuel \[T := \sum_{i=1}^\infty x_i.\] We will worry about the upper limit later, but right now it doesn’t matter since the way this formula is written, \(x_i = 0\) for all sufficiently large \(i\) and summing over those doesn’t hurt.
Let’s postpone the \(\max(\cdot\,, 0)\) part, and define the simpler sequence \(y_n\) by \({y_0 := x_0 = m}\) and, for \(i \geq 0\), \[\tag{2} y_{i+1} = \left\lfloor\frac{y_i}{3}\right\rfloor - 2.\] We can then compute \(T\) as \[T = \sum_{i=1}^\infty \max(y_i, 0)\] instead.
Equation (2) does not iterate cleanly, but it does if we add 3 to both sides. One way to motivate this is to note that \(y_i\) converges quickly to \(-3\), i.e. \(y_i + 3\) converges to 0. Concretely:
\[y_{i+1} + 3 = \left\lfloor\frac{y_i}{3}\right\rfloor - 2 + 3 = \left\lfloor\frac{y_i + 3}{3}\right\rfloor.\]
In other words, if we define \(z_i = y_i + 3\) for all \(i\), we have \[z_{i+1} = \left\lfloor\frac{z_i}{3}\right\rfloor,\] which implies \[z_{i} = \left\lfloor\frac{z_0}{3^i}\right\rfloor = \left\lfloor\frac{m + 3}{3^i}\right\rfloor\] for all \(i\); and we have \[\tag{3} T = \sum_{i=1}^\infty \max(z_i - 3, 0).\] We can compute a concrete upper bound for the sum now. The last index \(i\) we want is the last one where \(\lfloor z_0/3^i \rfloor \geq 3\). The flooring doesn’t actually matter here; we just want the largest \(i\) such that \(z_0 \geq 3^{i+1}\), which gives \(i \leq (\log_3 z_0) - 1\). So we can write \[\tag{4} T = \sum_{i=1}^{\lfloor \log_3 z_0 \rfloor - 1} (z_i - 3) = \sum_{i=1}^{\lfloor \log_3 (m+3) \rfloor - 1} \left(\left\lfloor\frac{m + 3}{3^i}\right\rfloor - 3\right).\] This is kind of similar to a closed form — we don’t have any recurrences any more, just a sum of elementary operations. But we can keep going, and in particular pin down the asymptotic behavior of \(T\) with \(m\).
Let’s write \(z_0 = m + 3\) in base 3. That is, suppose the digits of \(z_0\) in base 3 are \(a_n, a_{n-1}, \ldots, a_0\), which we may denote \[z_0 = \overline{(a_na_{n-1}a_{n-2}\ldots a_0)}_3,\] i.e. \[z_0 = \sum_{j=0}^n 3^ja_j,\quad a_j \in \{0, 1, 2\}, a_n \neq 0.\] The reason this is useful is that dividing a base-3 number by 3 and rounding down is simply chopping off the last digit. As a result, if \(0 \leq i \leq n\), then \[z_i = \overline{(a_na_{n-1}a_{n-2}\ldots a_i)}_3 = \sum_{j=0}^{n-i} 3^ja_{i+j},\] and the last \(z_i\) we can sum in (3) while ignoring the \(\max(\cdot\,,0)\) operation is \[z_{n-1} = \overline{(a_na_{n-1})}_3.\] So in fact (3) becomes \[\tag{5} T = \sum_{i=1}^{n-1} (z_i - 3) = \left(\sum_{i=1}^{n-1} z_i\right) - 3(n-1).\] Let’s focus on the sum \[\sum_{i=1}^{n-1} z_i = \sum_{i=1}^{n-1} \sum_{j=0}^{n-i} 3^ja_{i+j},\] and write down all terms involving a particular digit \(a_s\): it’s just \[a_s3^{s-1} + \cdots + a_s3^0\] (which we take to be the empty sum if \(s = 0\)), with an exception if \(s = n\), where the term \(a_n3^0\) does not appear because we stop slightly prematurely, before \(z_n\). This is a geometric series, which we can evaluate to be \[a_s \cdot \frac{3^s - 1}{2}.\] Therefore, \[\sum_{i=1}^{n-1} z_i = \left(\sum_{s=0}^n a_s\cdot \frac{3^s - 1}{2}\right) - a_n,\] where the \(-a_n\) term handles the exception pointed out above. With some rearrangement, we see \[\sum_{i=1}^{n-1} z_i = \frac{1}{2}\left(\sum_{s=0}^n (a_s3^s - a_s)\right) - a_n.\] But \(\sum_{s=0}^n a_s3^s\) is just \(z_0\), so \[\sum_{i=1}^{n-1} z_i = \frac{1}{2}\left(z_0 - \sum_{s=0}^n a_s\right) - a_n.\] If we substitute back into (5) we see \[T = \frac{1}{2}\left(z_0 - \sum_{s=0}^n a_s\right) - a_n - 3(n-1).\]
So, suppose \(m\) is the original module mass. If we write \(m + 3 = z_0\) in base 3, let \(S\) be the ternary digit sum, \(F\) be the first digit, and \(D\) be the number of digits (note that \(D = n + 1\)), then this equation becomes \[\tag{6} T = \frac{m}{2} - \frac{S}{2} - F - 3D + \frac{15}{2}.\]
The “closed form” (6) is much wordier than (4), but it’s a better “closed form” in the sense that the asymptotic behavior of \(T\) as a function of \(m\) is much more obvious: \[T = \frac{m}{2} - O(\log m).\] For large modules, the total mass of required fuel is roughly half of the mass of the module.