Fractal Exploration

It is impossible to approach this problem without both a healthy knowledge of combinatorics, and an arbitrary-size-integer programming language at your disposal. Even with these, some memoization tactics, and well-structured recursion, go a long way.

It's clear from the problem statement that the function we're considering here is absolutely explosive, so any approach which computes it linearly, or even in polynomial time, is likely to take far too long. We need to identify a succinct, recursive relationship that defines the number we're looking for.

---

Let $f(n)$ be the number of ways there are to fully explore an image of size $2^n \times 2^n$ . We seek the digit-sum of $f(9)$ , and to get that, we'll need to compute $f(9)$ . We'll set $f(0) = 1$ and $f(1) = 1$ as our base-cases, and let recursion decide the rest.

We immediately denote a useful auxiliary function, $s(n)$ , the number of steps it takes to fully explore a landscape of size $2^n \times 2^n$ . It should be clear that $s(n)$ is merely the geometric series:

$s(n) = 1 + 4^1 + 4^2 + ... + 4^{n-1} = \frac{4^n - 1}{4 - 1}$

Exploring the first pixel of an image of size $2^n \times 2^n$ immediately reveals four pixels of size $2^{n-1} \times 2^{n-1}$ , and this shall be the basis of our recursion. All of the sub-regions are disjoint, each one can be fully-revealed in $s(n-1)$ steps, and in $f(n-1)$ different ways. How many ways can we take these $4s(n-1)$ steps?

Clearly, we can take steps within the different regions in any order we like - one step in top-left, then two in bottom-left, one in top-right, one in top-left again, three in bottom-right... the number of ways we can make these moves, recognizing distinction only in terms of the quadrants they are made in, is equal to the quadrinomial coefficient :

$\binom{4s(n-1)}{s(n-1),s(n-1),s(n-1),s(n-1)} = \frac{(4s(n-1))!}{(s(n-1)!)^4}$

Independently, within each quadrant, we can order the steps made in that quadrant in $f(n-1)$ ways. Therefore, we have the recursive relationship:

$f(n > 1) = \binom{4s(n-1)}{s(n-1),s(n-1),s(n-1),s(n-1)}\:\cdot\:f^4(n-1)$

By caching the values for $f(n)$ , and computing the quadrinomial efficiently, we can compute $f(9)$ in just a handful of seconds on a modern computer.

---

And the digit sum of $f(9)$ is $\boxed{1663263}$