← Complete problem index

PROJECT EULER · #0980

The Quaternion Group I

Statement only · UnsolvedOriginal problem ↗

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, e.g. "xy" → "yx", "zx" → "xz", etc.

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

We define a sequence (an)n≥0: a0=88888888 and an=(8888⋅an−1)mod888888883 for n>0.

Let bn=anmod3. For each i≥0, a string c(i) of length 50 is defined by translating the finite sequence b50i,b50i+1,…,b50i+49 via the rule: 0→ "x", 1→ "y", 2→ "z".

Let F(N) be the number of ordered pairs (i,j) with 0≤i,j<N such that the concatenated string c(i)c(j) is neutral.
For example, F(10)=13 and F(100)=1224.

Find F(106).

Write-up coming later

The complete problem is available here. An approach, code, and answer will be added later.