Multiply

we can consider moves in the N,S,E,W directions as completely independent from those in the NE,SE,NW,and SW directions as no multiple of 1/sqrt2 is an integer.
if n moves are dedicated to the NE,SE,NW,and SW we can reach ${(n+1)}^{2}$ points from the original point (even or odd(depending on n) multiple of 1/sqrt2 coordinates).
thus from any lattice point reached in N steps we can reach ${((1000-N)+1)}^{2}$ points).
consider the number of lattice points we can reach in N steps.
considering we don't go back(towards the centre) we can reach 4N lattice points. those we can reach by going back will be counted in smaller values of N.
thus our expression is .
$\sum_{N=1}^{1000}$ 4N ${(1001-N)}^{2}$ =334668334000.
adding $1001^{2}$ points for N=0 we have 334669336001

Here's a slightly easier approach. Start off as Daniel did, and realize that we need to solve for solutions to

$|a| + |b| + |c| + |d| = 2k$

where $k = 0$ to 500.

The number of solutions for $k=0$ is clearly just $1$ .

Let's consider the number of solutions for $k \geq 1$ .
* If none of $a, b, c, d$ are 0 (1 way), then we need to solve for positive integer solutions to $w + x + y + z = 2k$ , and multiply by $2^4$ to account for signage. Thus, there are $1 \times 2^ 4 \times { 2k-1 \choose 3 }$ solutions.
* If exactly1 of $a, b, c, d$ is 0 (4 ways), then we need to solve for positive integer solutions to $w + x + y = 2k$ , and multiply by $2^3$ to account for signage. Thus, there are $4 \times 2^3 { 2k - 1 \times \choose 2 }$ solutions.
* If exactly 2 of $a, b, c, d$ is 0 (6 ways), then there are $6 \times 2^2 \times { 2k-1 \choose 1 }$ solutions.
* If exactly 3 of $a, b, c, d$ is 0 (4 ways), then there are $4 \times 2 \times { 2k-1 \choose 0 }$ solutions.
* If exactly 4 of $a, b, c, d$ are 0, then there are no solutions.

Hence, there are $\frac{64k^3 + 32 k } { 3}$ solutions to the equation.

Summing up from $k = 1$ to 500, we obtain 334669336000.

Adding the solution when $k = 0$ , there are 334669336001 in total.

---

Note: This approach easily generalizes counting the number of solutions to $|a| + |b| + \ldots + |k| = n$ .

The merging rule is what makes this problem difficult. As can be seen in the animation, merging starts early at $t = 2$ , and continues onwards with increasing complexity. Let's start with an easier problem. Let's define a 'step' to be a single replication in a single direction, and for the moment, let's keep replication down to just $4$ directions instead of $8$ , going in the strict cardinal directions.

The first thing we need to recognize is that snowflakes which exist at even times have positions entirely disjoint from those that exist at odd times. This is because, for any snowflake coordinates $(x, y)$ , $|x| + |y|\:\text{mod}\:2$ is invariant for any given $t$ . Given this information, we'll ask another question: How many snowflakes exist at positions at time $t$ , where no snowflakes existed at time $t - 2$ ? Any point reachable at time $t - 2$ is trivially reachable at time $t$ by simply adding a left and right step to cancel each other out. We call this restricted function $D(t)$ . Then the answer to our original question is thus (assuming $t$ even):

$S(t) = \sum_{k=0}^{t/2} D(2k)$

We set $D(0) = 1$ for correctness. So, going in $4$ directions, we find that $D(0) = 1$ , $D(2) = 8$ , $D(4) = 16$ , and, in general, $D(t > 0) = 4t$ , which is easily seen geometrically by the fact that the points accounting for the value $D(t)$ form a discrete diamond perimeter, expanding $4$ units every step. We can easily compute $S(t)$ using Euler's formula in this case.

However, now we must go back to the original problem with $8$ cardinal directions. We don't get a nice discrete diamond perimiter to use here, though... however, we'll realize that, if we again restrict ourself to $4$ directions, but using the diagonals this time, we see the same pattern emerge at a different rotation. Additionally, we'll note that every point in the $8$ direction space is of the form:

$(m_1 + n_1\frac{\sqrt{2}}{2}, m_2 + n_2\frac{\sqrt{2}}{2})$

And since $\sqrt{2}$ is irrational, any such point has unique representation - the tuple of integers $(m_1, n_1, m_2, n_2)$ is unique for any such point. Therefore, the points can be represented as:

$(m_1, m_2) + (m_1\frac{\sqrt{2}}{2}, n_1\frac{\sqrt{2}}{2})$

Which is just the sum of two vectors, one from each cartesian lattice! So, for given $m$ and $n$ , the points that can be reached in $m$ steps, but not $m - 2$ , in one lattice, and in $n$ steps, but not $n - 2$ , in the other lattice, are unique to the pair $(m, n)$ . For $m, n > 0$ , the number of such points is $(4m)(4n) = 16mn$ , and the pairs are fully described by the constraints $0 \leq m, n \leq m + n \leq t$ , and $m + n \equiv t\:\text{mod}\:2$ . So, we let $X = t/2$ , $t$ even, and we get the formula:

$S(t) = 1 + \sum_{k=1}^{X} 4(2k) + \sum_{q=1}^{X} 4(2q) + \sum_{k=0}^{X-1} \left( \sum_{q=0}^{X-k-1} 16(2k+1)(2q+1) \right) + \sum_{k=1}^{X-1} \left( \sum_{q=1}^{X-k} 16(2k)(2q) \right)$

Using some factoring, some algebra, and the first three instances of Faulhaber's Formula , we can reduce the entire expression down to:

$S(t) = \frac{16}{3} (X^4 + 2X^3 + 2X^2 + X) + 1$

Recall that $X = 500$ , plug into a calculator (or use a bunch of scratch paper), and we get the answer $\boxed{334669336001}$ .

I have used 2 days to solve this question.

I created three functions to solve this question, with F(n) being the answer with n iterations.

\[s(n) = \left\{\begin{array}{}1 \mbox{ if } n=0\\4n \mbox{ otherwise}\end{array}\right.\] $f(n) = \sum_{i=0}^n s(i)s(n-i)$ \[F(n) = \left\{\begin{array}{}f(n)+f(n-2)+f(n-4)+...+f(0) \mbox{ if 2|n} \\ f(n)+f(n-2)+f(n-4)+...+f(1) \mbox{ otherwise}\end{array}\right.\]

s(n) is a dummy function which returns 1,4,8,12,16,..., which is the number of points obtained if one is to walk in any 4 orthogonal directions for n steps without turning back.

f(n) is the number of points obtained by walking for n steps without turning back.

F(n) is the answer.

I used a computer to obtain the value of F(1000).

Or maybe i plotted the whole thing out and counted it up? Very pretty GIF! It reminds me of supernova simulations.