Solution

Answer: 124999683766

Project Euler 980 — “The Quaternion Group I”

Mathematical analysis

The title is the key hint: this is the quaternion group $Q_8$.

Map

$$x \mapsto i,\qquad y \mapsto j,\qquad z \mapsto k$$

with quaternion relations

$$i^2=j^2=k^2=-1,\qquad ij=k,\quad jk=i,\quad ki=j,$$

$$ji=-k,\quad kj=-i,\quad ik=-j.$$

Step 1 — Interpret the allowed moves

Move A: inserting $xx,yy,zz$

Example:

$$xx \mapsto i^2=-1.$$

So this multiplies the quaternion value by $-1$.

Move B: replacing

$$x\to yz,\qquad y\to zx,\qquad z\to xy$$

because

$$jk=i,\qquad ki=j,\qquad ij=k.$$

So the quaternion value is unchanged.

Move C: swapping adjacent distinct letters

Example:

$$xy \leftrightarrow yx.$$

But

$$ij=k,\qquad ji=-k.$$

Swapping different neighboring letters multiplies the value by $-1$.

Step 2 — The parity invariant

Each operation flips the sign of the quaternion value exactly once:

insert $aa$: multiply by $-1$,
replacement: step parity changes while value unchanged,
swap: multiply by $-1$.

Starting from the empty string with value $1$, after:

an even number of steps → value $1$,
an odd number of steps → value $-1$.

Therefore:

A string is neutral iff its quaternion product equals $1$.

That completely characterizes neutrality.

Step 3 — Computing $F(N)$

Each block $c(i)$ has length $50$.

Define its quaternion value:

$$q_i \in Q_8.$$

Then

$$c(i)c(j)\text{ is neutral} \iff q_i q_j = 1 \iff q_j = q_i^{-1}.$$

So we only need to count how many blocks evaluate to each quaternion element.

Step 4 — Quaternion multiplication table

The eight elements are

$$1,-1,i,-i,j,-j,k,-k.$$

Their inverses are:

$$1^{-1}=1,\quad (-1)^{-1}=-1,$$

$$i^{-1}=-i,\quad (-i)^{-1}=i,$$

$$j^{-1}=-j,\quad (-j)^{-1}=j,$$

$$k^{-1}=-k,\quad (-k)^{-1}=k.$$

If $cnt[g]$ is the number of blocks with value $g$, then

$$F(N)=\sum_{g\in Q_8} cnt[g]\cdot cnt[g^{-1}].$$

Python implementation

MOD = 888_888_883
A = 88_888_888
MULT = 8888

# Quaternion elements:
# 0:  1
# 1: -1
# 2:  i
# 3: -i
# 4:  j
# 5: -j
# 6:  k
# 7: -k

# Multiplication table
mul = [[0] * 8 for _ in range(8)]

names = ["1", "-1", "i", "-i", "j", "-j", "k", "-k"]
idx = {v: i for i, v in enumerate(names)}

base = {
    ("1", "1"): "1",
    ("1", "i"): "i",
    ("1", "j"): "j",
    ("1", "k"): "k",

    ("i", "1"): "i",
    ("j", "1"): "j",
    ("k", "1"): "k",

    ("i", "i"): "-1",
    ("j", "j"): "-1",
    ("k", "k"): "-1",

    ("i", "j"): "k",
    ("j", "k"): "i",
    ("k", "i"): "j",

    ("j", "i"): "-k",
    ("k", "j"): "-i",
    ("i", "k"): "-j",
}

def qmul(a, b):
    sa = -1 if a.startswith("-") else 1
    sb = -1 if b.startswith("-") else 1

    aa = a[1:] if a.startswith("-") else a
    bb = b[1:] if b.startswith("-") else b

    r = base[(aa, bb)]

    sr = -1 if r.startswith("-") else 1
    rr = r[1:] if r.startswith("-") else r

    sign = sa * sb * sr

    if rr == "1":
        return "1" if sign == 1 else "-1"

    return rr if sign == 1 else "-" + rr

# Build numeric multiplication table
for i, a in enumerate(names):
    for j, b in enumerate(names):
        mul[i][j] = idx[qmul(a, b)]

# map:
# x -> i
# y -> j
# z -> k
letter_map = [2, 4, 6]

N = 10**6

counts = [0] * 8
a = A

for _ in range(N):

    q = 0  # quaternion value starts at 1

    for _ in range(50):
        b = a % 3
        q = mul[q][letter_map[b]]
        a = (MULT * a) % MOD

    counts[q] += 1

inverse = [0, 1, 3, 2, 5, 4, 7, 6]

answer = 0
for g in range(8):
    answer += counts[g] * counts[inverse[g]]

print(answer)

Code walkthrough

Quaternion encoding

We encode:

ID	Value
0	1
1	-1
2	i
3	-i
4	j
5	-j
6	k
7	-k

mul[a][b] stores the product.

RNG generation

The sequence is:

$$a_n = 8888 a_{n-1}\pmod{888888883}.$$

For every generated value:

b = a % 3

we map:

0 → $i$,
1 → $j$,
2 → $k$.

Each block uses exactly 50 symbols.

Counting blocks

For each block we compute its quaternion product q.

Then:

counts[q] += 1

Final counting

A pair contributes iff:

$$q_i q_j = 1.$$

Thus:

counts[g] * counts[inverse[g]]

for every group element $g$.

Verification

The program reproduces the examples:

$F(10)=13$
$F(100)=1224$

exactly.

Running the full computation for $N=10^6$ gives:

$$124999683766.$$

Answer: 124999683766

Project Euler Problem 980