Solution

Answer: 271197444

Let

$A(n)$ = number of unit triangles that are exactly one layer thick,
$B(n)$ = number of unit triangles that are exactly three layers thick,
$G(n)=\gcd(A(n),B(n))$.

We are asked for

$$\sum_{n=3}^{10^7} G(n).$$

1. Mathematical analysis

The key step is to derive closed forms for $A(n)$ and $B(n)$.

By analyzing how the recursive overlay operation grows from order $n-1$ to order $n$, one obtains the linear recurrences

$$A(n)=4A(n-1)+2\cdot 3^{n-2},$$

$$B(n)=4B(n-1)+24(n-2)4^{n-3}-6\cdot 3^{n-2},$$

with initial values coming from the small snowflakes.

Solving these recurrences gives the explicit formulas

$$A(n)=3\cdot 4^{n-1}-2\cdot 3^{n-1},$$

and

$$B(n)=18(n-2)4^{n-2}+(4n+26)3^{n-1}-138\cdot 4^{n-2}.$$

These simplify to

$$B(n)= (18n-138)4^{n-2} + (4n+26)3^{n-1}.$$

Now compute the gcd.

Factor $A(n)$:

$$A(n)=3\left(4^{n-1}-2\cdot 3^{n-2}\right).$$

After algebraic elimination between $A(n)$ and $B(n)$, one finds

$$G(n) = 6\cdot \gcd!\left( 2\cdot 4^{n-2}-3^{n-2}, , 7n+3 \right).$$

That is the crucial simplification.

Further modular simplification

Let

$$m=7n+3.$$

If $3\nmid n$, then $\gcd(3,m)=1$, so $3^{n-2}$ is invertible modulo $m$.

Define

$$b \equiv 4\cdot 3^{-1} \pmod m.$$

Then

$$2\cdot 4^{n-2}-3^{n-2} \equiv 3^{n-2}\left(2b^{n-2}-1\right) \pmod m.$$

Since $3^{n-2}$ is invertible modulo $m$,

$$\gcd!\left(2\cdot 4^{n-2}-3^{n-2},m\right) = \gcd!\left(2b^{n-2}-1,m\right).$$

So each term can be computed using only modular exponentiation.

The complexity is essentially

$$O!\left(N\log N\right),$$

which is easily fast enough for $N=10^7$.

2. Python implementation

from math import gcd

def A(n):
    return 3 * pow(4, n - 1) - 2 * pow(3, n - 1)

def B(n):
    p4 = pow(4, n - 2)
    p3 = pow(3, n - 1)
    return (18 * n - 138) * p4 + (4 * n + 26) * p3

def G(n):
    m = 7 * n + 3

    # If gcd(3, m) = 1, cancel 3^(n-2) modulo m
    if n % 3 != 0:

        # modular inverse of 3 modulo m
        if m % 3 == 1:
            inv3 = (2 * m + 1) // 3
        else:
            inv3 = (m + 1) // 3

        b = (4 * inv3) % m

        t = pow(b, n - 2, m)

        return 6 * gcd((2 * t - 1) % m, m)

    # Otherwise compute directly
    x = (2 * pow(4, n - 2, m) - pow(3, n - 2, m)) % m

    return 6 * gcd(x, m)

def solve(N):
    total = 0

    for n in range(3, N + 1):
        total += G(n)

    return total

# Verification against the statement
assert A(3) == 30
assert B(3) == 6
assert G(3) == 6

assert A(11) == 3027630
assert B(11) == 19862070
assert G(11) == 30

assert G(500) == 186
assert solve(500) == 5124

print(solve(10_000_000))

3. Code walkthrough

Closed forms

def A(n):

Implements

$$A(n)=3\cdot 4^{n-1}-2\cdot 3^{n-1}.$$

def B(n):

Implements the derived formula for $B(n)$.

Computing $G(n)$

We use

$$G(n) = 6\cdot \gcd!\left( 2\cdot 4^{n-2}-3^{n-2}, 7n+3 \right).$$

m = 7 * n + 3

The modulus appearing in the gcd identity.

If $n\not\equiv0\pmod3$, then $3$ is invertible modulo $m$, so we reduce the expression to a single modular exponentiation.

t = pow(b, n - 2, m)

Efficient modular exponentiation in $O(\log n)$.

return 6 * gcd((2 * t - 1) % m, m)

Exactly computes $G(n)$.

4. Verification

The program reproduces all values given in the problem statement:

$A(3)=30$
$B(3)=6$
$G(3)=6$

and

$A(11)=3027630$
$B(11)=19862070$
$G(11)=30$

Also:

$$G(500)=186,$$

and

$$\sum_{n=3}^{500} G(n)=5124,$$

matching the statement perfectly.

Running the full computation for $10^7$ gives:

$$271197444.$$

Answer: 271197444

Project Euler Problem 570