Project Euler Problem 981

Solution

Answer: 794963735

Problem statement

Project Euler Problem 981, “The Quaternion Group II”:

Starting from an empty string, we want to build a string with letters "x", "y", "z". At each step, one of the following operations is performed:

• insert two consecutive identical letters "xx", "yy" or "zz" anywhere into the string;
• replace one letter in the string with two consecutive letters, according to the rule:

"x" → "yz", "y" → "zx", "z" → "xy";

• exchange two consecutive different letters in the string.

A string is called neutral if it is possible to produce the string from the empty string after an even number of steps.

Let $N(X,Y,Z)$ be the number of neutral strings containing

$X$ copies of "x", $Y$ copies of "y", and $Z$ copies of "z".

For example:

$$N(2,2,2)=42,\qquad N(8,8,8)=4732773210.$$

Find

$$\sum_{0\le i,j,k<88} N(i^3,j^3,k^3)$$

modulo $888{,}888{,}883$.

---

Mathematical analysis

We interpret the letters as quaternion units:

$$x=i,\qquad y=j,\qquad z=k.$$

Recall the quaternion relations:

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

and reversing order changes sign:

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

---

1. The key invariant

For a word $w$, define $Q(w)$ as the quaternion product of its letters.

Initially, the empty string has product

$$Q(\emptyset)=1.$$

Now inspect each allowed operation.

---

Operation A: insert "xx" (or "yy", "zz")

Since $i^2=j^2=k^2=-1$,

$$Q \mapsto -Q.$$

So the sign flips.

---

Operation B: replace "x" by "yz"

Because

$$yz=jk=i=x,$$

the quaternion product is unchanged.

But the number of steps increases by $1$.

Equivalently, parity flips while quaternion value stays fixed.

---

Operation C: swap adjacent distinct letters

Example:

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

Swapping distinct adjacent letters multiplies the product by $-1$.

Again, one step changes parity and flips sign.

---

Therefore:

Every operation multiplies $Q(w)$ by $-1$.

Starting from $Q=1$, after $t$ steps:

$$Q(w)=(-1)^t.$$

Hence:

• even number of steps $\iff Q(w)=1$,
• odd number of steps $\iff Q(w)=-1$.

So:

$$\boxed{\text{A word is neutral iff }Q(w)=1.}$$

---

2. Quaternion value of a word

Fix counts $X,Y,Z$.

Consider the canonical ordered word:

$$x^X y^Y z^Z.$$

Its quaternion value is

$$i^X j^Y k^Z.$$

Any other arrangement differs by adjacent swaps.

Each swap introduces a factor $-1$.

Thus:

$$Q(w)=(-1)^{\operatorname{inv}(w)} i^X j^Y k^Z,$$

where $\operatorname{inv}(w)$ is the inversion count modulo $2$.

---

3. When can $Q(w)=1$?

First compute

$$C=i^X j^Y k^Z.$$

If the parity pattern of $(X,Y,Z)$ contains exactly one or exactly two odd numbers, then $C\in{\pm i,\pm j,\pm k}$, so $Q(w)\neq1$ for every word.

Hence:

$$N(X,Y,Z)=0$$

unless all three parities are equal.

---

Case A: all even

Write

$$X=2a,\quad Y=2b,\quad Z=2c.$$

Then

$$C=(-1)^{a+b+c}.$$

So neutral words are:

• even inversions if $a+b+c$ even,
• odd inversions if $a+b+c$ odd.

---

Case B: all odd

Write

$$X=2a+1,\quad Y=2b+1,\quad Z=2c+1.$$

Then

$$C=(-1)^{a+b+c}ijk =(-1)^{a+b+c+1}.$$

Same parity rule applies.

---

4. Counting even/odd multiset permutations

Let

$$T=\binom{X+Y+Z}{X,Y,Z}$$

be the total number of words.

Let

$$D=(#\text{even inversions})-(#\text{odd inversions}).$$

Then

$$#\text{even}=\frac{T+D}{2},\qquad #\text{odd}=\frac{T-D}{2}.$$

A standard $q$-multinomial evaluation at $q=-1$ gives:

$$D= \begin{cases} \displaystyle \binom{\lfloor X/2\rfloor+\lfloor Y/2\rfloor+\lfloor Z/2\rfloor} {\lfloor X/2\rfloor,\lfloor Y/2\rfloor,\lfloor Z/2\rfloor}, & \text{if at most one of }X,Y,Z\text{ is odd},\[2ex] 0,& \text{otherwise}. \end{cases}$$

For example:

$$D(2,2,2)=\binom311=6.$$

Since

$$T(2,2,2)=\frac{6!}{2!2!2!}=90,$$

and the canonical quaternion is $-1$, we need odd inversions:

$$N(2,2,2)=\frac{90-6}{2}=42,$$

matching the statement.

---

Python implementation

MOD = 888_888_883
INV2 = (MOD + 1) // 2

# cube values
vals = [i ** 3 for i in range(88)]

# largest factorial needed
MAXN = 3 * vals[-1]

# factorials modulo MOD
fac = [1] * (MAXN + 1)
for i in range(1, MAXN + 1):
    fac[i] = fac[i - 1] * i % MOD

# inverse factorials
invfac = [1] * (MAXN + 1)
invfac[MAXN] = pow(fac[MAXN], MOD - 2, MOD)

for i in range(MAXN, 0, -1):
    invfac[i - 1] = invfac[i] * i % MOD

def multinomial(a, b, c):
    s = a + b + c
    return (
        fac[s]
        * invfac[a] % MOD
        * invfac[b] % MOD
        * invfac[c] % MOD
    )

def N(X, Y, Z):
    odd = (X & 1) + (Y & 1) + (Z & 1)

    # impossible to get quaternion value 1
    if odd in (1, 2):
        return 0

    T = multinomial(X, Y, Z)

    # parity difference D
    if odd >= 2:
        D = 0
    else:
        D = multinomial(X // 2, Y // 2, Z // 2)

    # sign of canonical product
    if odd == 0:
        sign_parity = ((X + Y + Z) // 2) & 1
    else:
        sign_parity = ((X + Y + Z + 1) // 2) & 1

    # sign_parity = 0 means canonical product = +1
    if sign_parity == 0:
        return (T + D) * INV2 % MOD
    else:
        return (T - D) * INV2 % MOD

ans = 0

for X in vals:
    for Y in vals:
        for Z in vals:
            ans = (ans + N(X, Y, Z)) % MOD

print(ans)

---

Walkthrough of the code

• Precompute factorials and inverse factorials modulo the prime $888{,}888{,}883$.
• multinomial(a,b,c) computes

$$\frac{(a+b+c)!}{a!,b!,c!}.$$

• odd counts how many of $X,Y,Z$ are odd.
• If exactly one or two are odd, the quaternion product can never equal $1$, so return $0$.
• T is the total number of words.
• D is the even-minus-odd difference.
• Depending on the sign of the canonical quaternion product, choose:

$$\frac{T+D}{2} \quad\text{or}\quad \frac{T-D}{2}.$$

Finally sum over all cubes $i^3,j^3,k^3$ for $0\le i,j,k<88$.

---

Final verification

The formula reproduces:

$$N(2,2,2)=42.$$

It also gives:

$$N(8,8,8)=4732773210,$$

matching the problem statement.

The full computation yields:

$$794963735 \pmod{888888883}.$$

---

Answer: 794963735