Detailed mathematical approach

Problem Summary

For integers \(m\ge2\) and \(n\ge1\), we place \(mn\) toppings around a circle, with exactly \(n\) copies of each of the \(m\) colors. Two arrangements are considered the same if one is a rotation of the other. Let \(f(m,n)\) be the number of distinct rotational classes. The Project Euler task is to sum all values satisfying

$f(m,n)\le 10^{15}.$

The final numeric sum is intentionally omitted here; the goal is to explain the counting formula and the search bounds used by the C++ solution.

Mathematical Approach

1) Burnside's lemma is the natural tool

The acting group is the cyclic rotation group

$C_{mn}=\{0,1,\dots,mn-1\},$

where rotation by \(r\) means shifting every position by \(r\) places around the circle.

Burnside's lemma says that the number of rotational classes is the average number of arrangements fixed by each rotation:

$f(m,n)=\frac{1}{mn}\sum_{r=0}^{mn-1}\mathrm{Fix}(r).$

So the whole problem is to understand \(\mathrm{Fix}(r)\) for one rotation \(r\).

2) Cycle structure of one rotation

Set

$N=mn,\qquad d=\gcd(N,r).$

The rotation by \(r\) decomposes the \(N\) positions into

$d$

disjoint cycles, each of length

$\ell=\frac{N}{d}.$

This is the standard cycle decomposition of a cyclic shift.

An arrangement is fixed by this rotation if and only if every cycle is monochromatic: once one position in a cycle is chosen, all other positions in that cycle are forced to have the same color.

3) When can a rotation fix any valid arrangement?

Each color appears exactly \(n\) times. If every cycle has length \(\ell\), then every color must occupy a whole number of cycles. Therefore

$\ell \mid n$

is necessary.

It is also sufficient. If \(\ell\mid n\), then each color must occupy exactly

$\frac{n}{\ell}$

cycles, because each such cycle contributes \(\ell\) positions of that color.

Since there are

$d=\frac{N}{\ell}=\frac{mn}{\ell}$

cycles in total, a fixed arrangement exists precisely when \(\ell\mid n\).

4) Counting the fixed arrangements for one cycle length

Assume \(\ell\mid n\). Then the \(d=\frac{mn}{\ell}\) cycles are distinguishable cycle slots, and we must color them so that each of the \(m\) colors is used exactly \(\frac{n}{\ell}\) times.

So the number of fixed arrangements is the multinomial coefficient

$\mathrm{Fix}(\ell)=\frac{\left(\frac{mn}{\ell}\right)!}{\left(\frac{n}{\ell}!\right)^m}.$

If \(\ell\nmid n\), then

$\mathrm{Fix}(\ell)=0.$

5) How many rotations have the same cycle length?

Now fix a divisor \(\ell\) of \(N\). We want the number of rotations \(r\) whose cycle length is exactly \(\ell\), that is, whose gcd with \(N\) equals \(N/\ell\).

Write

$r=\frac{N}{\ell}k.$

Then

$\gcd(N,r)=\frac{N}{\ell}\gcd(\ell,k).$

So the condition \(\gcd(N,r)=N/\ell\) is equivalent to

$\gcd(\ell,k)=1.$

The number of such residues \(k\) modulo \(\ell\) is exactly Euler's totient:

$\varphi(\ell).$

Therefore there are \(\varphi(\ell)\) rotations with cycle length \(\ell\).

6) The divisor formula used by the code

Only divisors \(\ell\mid n\) contribute, so Burnside becomes

$f(m,n)=\frac{1}{mn}\sum_{\ell\mid n}\varphi(\ell)\, \frac{(mn/\ell)!}{\bigl((n/\ell)!\bigr)^m}.$

This is exactly the formula implemented by f_value() in the C++ solution.

7) Worked example: \(f(3,2)=16\)

Here \(m=3\), \(n=2\), so \(N=6\). The divisors of \(n\) are \(1\) and \(2\). Hence

$f(3,2)=\frac{1}{6}\left[ \varphi(1)\frac{6!}{(2!)^3}+ \varphi(2)\frac{3!}{(1!)^3} \right].$

Now

$\varphi(1)=1,\qquad \varphi(2)=1,$

so

$f(3,2)=\frac{1}{6}\left[\frac{720}{8}+6\right] =\frac{1}{6}(90+6)=16.$

This is one of the explicit checkpoints in the code.

8) Another small example: \(f(2,3)=4\)

With two colors and three copies of each,

$f(2,3)=\frac{1}{6}\left[ \varphi(1)\frac{6!}{(3!)^2}+ \varphi(3)\frac{2!}{(1!)^2} \right].$

Since \(\varphi(1)=1\) and \(\varphi(3)=2\), we get

$f(2,3)=\frac{1}{6}(20+4)=4.$

The brute-force checkpoint in the program confirms this value by explicit necklace enumeration.

9) Why the search over \(n\) is finite

The Burnside sum is positive-term, so just the identity rotation \(\ell=1\) already gives a lower bound:

$f(m,n)\ge \frac{1}{mn}\frac{(mn)!}{(n!)^m}=:g(m,n).$

For fixed \(n\), this lower bound increases with \(m\). Indeed,

$\frac{g(m+1,n)}{g(m,n)} =\frac{m}{m+1}\cdot \frac{\prod_{k=1}^{n}(mn+k)}{n!} >1.$

So among all \(m\ge2\), the smallest possible value occurs at \(m=2\). Therefore

$f(m,n)\ge g(2,n)=\frac{(2n)!}{2n\,(n!)^2} =\frac{1}{2n}\binom{2n}{n}.$

If this lower bound already exceeds \(10^{15}\), then no value with that \(n\) can contribute, for any \(m\ge2\).

This is exactly why the code computes

$\frac{1}{2n}\binom{2n}{n}$

in compute_n_upper_bound().

10) Why the search over \(m\) is finite

Take \(n=1\). Then we place \(m\) distinct colors once each around the circle, modulo rotation. The number of circular orders is

$f(m,1)=(m-1)!.$

So if

$ (m-1)! > 10^{15}, $

then even the smallest possible \(n\) already overshoots the limit, and this \(m\) can never contribute.

That is why compute_m_upper_bound() effectively finds the largest \(m\) with

$ (m-1)! \le 10^{15}. $

Code Logic

1) Totients. compute_totients() sieves all \(\varphi(\ell)\) values up to the maximum relevant \(n\).

2) Factorials and factorial powers. factorials_up_to() precomputes \(k!\), and precompute_fact_powers() stores \((n!)^m\). This avoids repeating huge multiplications in every Burnside term.

3) Burnside evaluator. f_value(m,n,...) loops over all divisors \(\ell\mid n\), computes the multinomial fixed-count term, multiplies by \(\varphi(\ell)\), sums, and divides by \(mn\).

4) Checkpoints. The code explicitly verifies

$f(2,1)=1,\qquad f(2,2)=2,\qquad f(3,1)=2,\qquad f(3,2)=16,$

and then compares the formula with brute-force necklace counting for

$ (m,n)\in\{(2,3),(2,4),(3,2),(4,2)\}. $

5) Final scan. After the safe upper bounds are known, the program checks every \((m,n)\) in that rectangle and adds only values \(\le10^{15}\).

Complexity Analysis

For each pair \((m,n)\), the work is proportional to the number of divisors of \(n\), plus big-integer arithmetic on factorial ratios. The precomputed totients, factorials, and factorial powers greatly reduce repeated work. Memory usage is dominated by those precomputed big-integer tables.

Further Reading

1. Problem page: https://projecteuler.net/problem=281
2. Burnside’s lemma: https://en.wikipedia.org/wiki/Burnside%27s_lemma
3. Pólya/Burnside counting for necklaces: https://en.wikipedia.org/wiki/P%C3%B3lya_enumeration_theorem