Detailed mathematical approach

Problem Summary

We colour the 24 visible stickers of a \(2\times 2\times 2\) Rubik's Cube using \(n\) available colours. Two colourings are considered equivalent if one can be transformed into the other by legal cube moves. The goal is to count the number \(N(n)\) of distinct orbit classes, with the published target \(n=10\) and the useful checkpoint \(N(2)=183\).

Mathematical Approach

This is an orbit-counting problem for the cube move group acting on 24 sticker positions. The implementations evaluate the same Burnside average in two equivalent ways: one by direct enumeration of all reachable cube states, and one by compressing the sum according to the cycle type of the corner permutation.

Step 1: Describe a Cube State by Corners and Twists

A legal \(2\times 2\times 2\) state is determined by a permutation of the 8 corner cubies together with a twist value \(o_i\in\{0,1,2\}\) for each corner. The twists are constrained by

$\sum_{i=1}^{8} o_i \equiv 0 \pmod{3}.$

So the number of reachable states is

$|G|=8!\cdot 3^7=88{,}179{,}840.$

This is the group over which Burnside's lemma is averaged.

Step 2: Apply Burnside's Lemma to Sticker Colourings

Each group element \(g\in G\) induces a permutation of the 24 stickers. Let \(c(g)\) be the number of cycles in that sticker permutation. A colouring is fixed by \(g\) if and only if every sticker cycle is monochromatic, so the number of fixed colourings is

$\operatorname{Fix}(g)=n^{c(g)}.$

Therefore the number of distinct colourings is

$N(n)=\frac{1}{|G|}\sum_{g\in G} n^{c(g)}.$

The entire problem is now reduced to understanding \(c(g)\) efficiently.

Step 3: Reduce the Cycle Count to Corner Cycles

Write the corner permutation of \(g\) as disjoint cycles. Consider one such corner cycle of length \(\ell\). If the twists encountered around that cycle are \(t_1,\dots,t_\ell\), define its total twist residue by

$S\equiv t_1+t_2+\cdots+t_\ell \pmod{3}.$

After following a sticker once around those \(\ell\) corners, the sticker returns to the starting corner but rotated by \(S\). That gives exactly two possibilities:

$\phi(S)= \begin{cases} 3,&S=0,\\ 1,&S\in\{1,2\}. \end{cases}$

If \(S=0\), the 3 local sticker tracks remain separate, giving 3 sticker cycles of length \(\ell\). If \(S=1\) or \(2\), those 3 tracks merge into a single sticker cycle of length \(3\ell\).

Step 4: Count Corner Permutations by Cycle Type

Let the corner permutation have cycle type

$\lambda=1^{m_1}2^{m_2}\cdots 8^{m_8},\qquad \sum_{r=1}^{8} r\,m_r=8.$

If

$k=\sum_{r=1}^{8} m_r$

is the number of corner cycles, then the number of corner permutations with this type is

$A(\lambda)=\frac{8!}{\prod_{r=1}^{8} r^{m_r}m_r!}.$

This is the standard formula for the number of permutations with a prescribed cycle decomposition.

Step 5: Count Twist Assignments for a Fixed Cycle Type

For the \(k\) corner cycles, record only their total twist residues \(S_1,\dots,S_k\in\{0,1,2\}\). The global twist rule becomes

$\sum_{j=1}^{k} S_j \equiv 0 \pmod{3}.$

If the \(j\)-th corner cycle has length \(\ell_j\), then once \(S_j\) is fixed there are \(3^{\ell_j-1}\) actual twist assignments on that cycle. Multiplying over all cycles gives

$\prod_{j=1}^{k} 3^{\ell_j-1}=3^{8-k}.$

So for a fixed cycle type \(\lambda\) and a fixed residue pattern \(S_1,\dots,S_k\) satisfying the congruence, there are exactly \(A(\lambda)\,3^{8-k}\) group elements with that local behaviour.

Step 6: Assemble the Compressed Burnside Formula

The sticker-cycle count contributed by the residue pattern is

$c=\sum_{j=1}^{k}\phi(S_j).$

Hence

$\boxed{ N(n)=\frac{1}{8!\,3^7} \sum_{\lambda\vdash 8} A(\lambda)\,3^{8-k} \sum_{\substack{S_1,\dots,S_k\in\{0,1,2\}\\ \sum S_j\equiv 0 \pmod{3}}} n^{\sum_{j=1}^{k}\phi(S_j)} }.$

This is the class-compressed form used by the Python and Java implementations. The C++ implementation evaluates the same quantity by enumerating every one of the \(8!\cdot 3^7\) reachable states directly and computing the corresponding 24-sticker cycle count.

Worked Example: One Corner Cycle of Length 2

Suppose one cycle of the corner permutation has length \(\ell=2\). It moves 2 corners and therefore 6 stickers.

If its total twist residue is \(S=0\), then those 6 stickers split into 3 separate 2-cycles, so this corner cycle contributes \(3\) to \(c(g)\).

If its total twist residue is \(S=1\) or \(2\), then the 3 sticker tracks feed into one another and all 6 stickers lie on a single 6-cycle, so the contribution is \(1\).

This local rule is the heart of the method: once the corner cycle structure and the twist sums modulo 3 are known, the number of fixed colourings is immediately \(n^{c(g)}\).

How the Code Works

The C++, Python, and Java implementations all compute the Burnside numerator

$\sum_{g\in G} n^{c(g)}$

in big-integer arithmetic and divide by \(8!\cdot 3^7\) at the end.

The C++ implementation explicitly generates all 8! corner permutations and all \(3^7\) valid twist vectors, constructs the induced permutation on 24 stickers, counts its cycle decomposition, and accumulates a histogram by sticker-cycle count. Once the histogram is known, the orbit count is evaluated as

$N(n)=\frac{1}{|G|}\sum_{k=0}^{24} f_k n^k,$

where \(f_k\) is the number of group elements having exactly \(k\) sticker cycles.

The Python and Java implementations avoid explicit 24-sticker permutations. Instead, they enumerate the partitions of 8, compute how many corner permutations have each cycle type, iterate over the admissible twist-sum residues for those cycles, and add the corresponding term \(n^c\) with multiplicity \(A(\lambda)\,3^{8-k}\). Both viewpoints are mathematically identical.

A practical checkpoint is

$N(2)=183,$

which confirms that the group size, twist constraint, and sticker-cycle logic are all consistent before evaluating the target case \(n=10\).

Complexity Analysis

The C++ implementation performs a direct traversal of all

$8!\cdot 3^7=88{,}179{,}840$

reachable states. Counting cycles on 24 stickers takes \(O(24)\) per state, so the total work is \(O(8!\cdot 3^7\cdot 24)\), with small extra memory for the global histogram and thread-local accumulators.

The Python and Java implementations are much more compressed. They iterate over the 22 partitions of 8 and, for a partition with \(k\) parts, over at most \(3^k\le 3^8\) residue patterns. Since the cube size is fixed, this is effectively constant-time orbit counting apart from big-integer arithmetic. Memory usage is \(O(1)\) beyond a small collection of partitions and counters.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=599
2. Burnside's lemma: Wikipedia — Burnside's lemma
3. Group action: Wikipedia — Group action
4. Rubik's Cube group: Wikipedia — Rubik's Cube group
5. Permutation cycle notation: Wikipedia — Permutation cycle notation