Detailed mathematical approach

Problem Summary

Problem 930 studies a gathering process on the cycle graph \(C_n\) with \(m\) walkers. The quantity \(F(n,m)\) is the average gathering time for that pair \((n,m)\), and the final target is

\[ G(12,12)=\sum_{n=2}^{12}\sum_{m=2}^{12}F(n,m). \]

The local implementations do not simulate the Markov chain step by step. Instead, they evaluate the spectral decomposition of the relative-position chain, then group equal Fourier modes together so the final sum runs over occupancy counts \(x_0,\dots,x_{n-1}\).

Mathematical Approach

The quotient state space and its Fourier basis

Only relative positions matter for gathering. If all walkers are shifted by the same amount around the cycle, the configuration is unchanged from the point of view of the meeting event. That means the natural state space is the quotient

\[ (\mathbb{Z}/n\mathbb{Z})^m \big/ \langle(1,\dots,1)\rangle. \]

Write \(\omega=e^{2\pi i/n}\). A Fourier character on \((\mathbb{Z}/n\mathbb{Z})^m\) has the form

\[ \chi_k(y_1,\dots,y_m)=\omega^{k_1y_1+\cdots+k_my_m}, \]

where \(k=(k_1,\dots,k_m)\in(\mathbb{Z}/n\mathbb{Z})^m\). Such a character descends to the quotient exactly when it is invariant under the diagonal shift \((y_1,\dots,y_m)\mapsto(y_1+1,\dots,y_m+1)\). That condition is

\[ k_1+\cdots+k_m\equiv 0 \pmod{n}. \]

Grouping modes by frequency counts

The implementations do not keep the ordered \(m\)-tuple \(k\) directly. They only need to know how many entries of \(k\) are equal to each residue \(r\in\{0,1,\dots,n-1\}\). Define

\[ x_r=\#\{j:k_j=r\}. \]

Then the admissible vectors satisfy

\[ \sum_{r=0}^{n-1}x_r=m, \qquad \sum_{r=0}^{n-1} r x_r\equiv 0 \pmod{n}. \]

So the summation is over the set

\[ \mathcal{C}_{n,m}= \left\{ x\in\mathbb{Z}_{\ge 0}^n: \sum_{r=0}^{n-1}x_r=m,\ \sum_{r=0}^{n-1} r x_r\equiv 0 \pmod{n} \right\}. \]

Many ordered frequency tuples produce the same occupancy vector \(x\). Their multiplicity is the multinomial coefficient

\[ W(x)=\frac{m!}{\prod_{r=0}^{n-1}x_r!}. \]

This is exactly what the implementations build incrementally with a product of binomial coefficients:

\[ \prod_{r=0}^{n-1} \binom{m-\sum_{s<r}x_s}{x_r} = \frac{m!}{\prod_{r=0}^{n-1}x_r!}. \]

The eigenvalue of one grouped mode

In one step of the gathering chain, one of the \(m\) walkers is chosen uniformly, then that walker moves one edge left or right with probability \(1/2\). For a single Fourier frequency \(r\), the transition operator contributes the factor

\[ \frac{\omega^r+\omega^{-r}}{2} = \cos\left(\frac{2\pi r}{n}\right). \]

If the whole mode is summarized by the occupancy vector \(x\), the corresponding eigenvalue is the average of those single-frequency factors:

\[ \lambda(x)= \frac{1}{m} \sum_{r=0}^{n-1}x_r\cos\left(\frac{2\pi r}{n}\right). \]

The averaged hitting-time formula for the quotient chain therefore becomes

\[ F(n,m)= \sum_{\substack{x\in\mathcal{C}_{n,m}\\x\neq(m,0,\dots,0)}} \frac{W(x)}{1-\lambda(x)}. \]

Written out explicitly, this is

\[ F(n,m)= \sum_{\substack{ x\in\mathbb{Z}_{\ge0}^n\\ \sum x_r=m\\ \sum r x_r\equiv 0\ (n)\\ x\neq(m,0,\dots,0) }} \frac{\dfrac{m!}{\prod_r x_r!}} {1-\dfrac{1}{m}\sum_{r=0}^{n-1}x_r\cos\left(\frac{2\pi r}{n}\right)}. \]

The excluded vector \(x=(m,0,\dots,0)\) is the constant Fourier mode. It has \(\lambda(x)=1\), so it corresponds to the stationary part and would make the denominator vanish. Every other admissible vector has \(\lambda(x)<1\), since \(\cos(2\pi r/n)\le 1\) and equality occurs only at \(r=0\).

Worked example: \(F(3,2)=\frac{4}{3}\)

For \(n=3\) and \(m=2\), the constraints are

\[ x_0+x_1+x_2=2, \qquad x_1+2x_2\equiv 0 \pmod{3}. \]

The only nontrivial solution is \(x=(0,1,1)\). Its multiplicity is

\[ W(x)=\frac{2!}{1!\,1!}=2. \]

Its eigenvalue is

\[ \lambda(x)= \frac{\cos(2\pi/3)+\cos(4\pi/3)}{2} = \frac{-1/2-1/2}{2} = -\frac{1}{2}. \]

So the contribution is

\[ F(3,2)=\frac{2}{1-(-1/2)}=\frac{2}{3/2}=\frac{4}{3}, \]

which agrees with the exact small case used by the implementations.

How the Code Works

Precomputation for one pair \((n,m)\)

The C++, Python, and Java implementations first build a Pascal-triangle table of binomial coefficients up to \(m\). They also precompute the list of cosine values \(\cos(2\pi r/n)\) for \(r=0,1,\dots,n-1\). Those two tables are enough to evaluate every grouped Fourier contribution.

Depth-first enumeration of admissible occupancy vectors

The main recursion distributes the total mass \(m\) across the \(n\) residues. At every stage it maintains the remaining mass, the partial residue sum modulo \(n\), the partial cosine sum, and the current combinatorial multiplicity. When the last residue is reached, the implementation checks the congruence condition, discards the trivial all-zero-frequency mode, computes the denominator \(1-\lambda(x)\), and adds \(W(x)/(1-\lambda(x))\) to the running total.

Because the multiplicity is accumulated incrementally from binomial choices, the code never has to construct \(m!\) or any large tuple of frequencies directly. It works only with the grouped occupancy data that matter mathematically.

Outer accumulation

After one value \(F(n,m)\) is finished, the outer loops add it into the grand total for all \(2\le n\le 12\) and \(2\le m\le 12\). The C++ implementation also checks several small exact values before producing the final scientific-notation output.

Complexity Analysis

For fixed \(n\) and \(m\), the recursion enumerates the weak compositions of \(m\) into \(n\) parts. Their count is

\[ \binom{m+n-1}{n-1}, \]

so the running time for one pair \((n,m)\) is of that order, up to constant work per branch and the \(O(m^2)\) preprocessing used to build the binomial table. The cosine table adds only \(O(n)\) work.

Therefore the total cost for the final answer is

\[ O\left( \sum_{n=2}^{12}\sum_{m=2}^{12} \binom{m+n-1}{n-1} \right), \]

with memory usage \(O(m^2+n)\) for the binomial table and cosine list, plus \(O(n)\) recursion depth. The important gain is that the algorithm sums grouped spectral terms directly instead of simulating an exponentially larger state graph.

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=930
2. Cycle graph: Wikipedia - Cycle graph
3. Discrete Fourier transform: Wikipedia - Discrete Fourier transform
4. Multinomial theorem: Wikipedia - Multinomial theorem
5. Hitting time: Wikipedia - Hitting time