Detailed mathematical approach

Problem Summary

Let \(C(m,n)\) denote the number of spanning trees of the \(m \times n\) rectangular grid graph. The Project Euler instance asks for the value at \((m,n)=(100,500)\), but the exact integer has more than twenty-five thousand decimal digits, so the implementations return the answer in scientific notation instead of constructing the full integer explicitly.

The local solution files all exploit the same fact: for this particular graph family, the Matrix-Tree theorem converts the counting problem into a product over explicit Laplacian eigenvalues.

Mathematical Approach

Step 1: Use the Matrix-Tree Theorem

For any connected graph \(G\) with Laplacian eigenvalues

$0=\lambda_0\lt\lambda_1\le \lambda_2 \le \dots \le \lambda_{|V|-1},$

Kirchhoff's Matrix-Tree theorem gives the spanning-tree count as

$\tau(G)=\frac{1}{|V|}\prod_{k=1}^{|V|-1}\lambda_k.$

In our case, the grid graph has \(mn\) vertices, so once the nonzero Laplacian eigenvalues are known, we immediately obtain \(C(m,n)\).

Step 2: Laplacian Eigenvalues of the Rectangular Grid

The \(m \times n\) rectangular grid is the Cartesian product of two path graphs, one of length \(m\) and one of length \(n\). For the path graph with \(m\) vertices, the Laplacian eigenvalues are

$\alpha_i=2-2\cos\frac{\pi i}{m},\qquad i=0,1,\dots,m-1,$

and similarly for the path graph with \(n\) vertices,

$\beta_j=2-2\cos\frac{\pi j}{n},\qquad j=0,1,\dots,n-1.$

For a Cartesian product, Laplacian eigenvalues add, so the grid eigenvalues are

$\lambda_{i,j}=\alpha_i+\beta_j=4-2\cos\frac{\pi i}{m}-2\cos\frac{\pi j}{n}.$

The pair \((i,j)=(0,0)\) gives the single zero eigenvalue corresponding to the constant vector. Every other pair gives a positive eigenvalue because the grid graph is connected.

Step 3: Closed Product Formula for \(C(m,n)\)

Substituting the grid eigenvalues into Kirchhoff's formula yields

$\boxed{C(m,n)=\frac{1}{mn}\prod_{\substack{0 \le i \lt m\\0 \le j \lt n\\ (i,j)\ne(0,0)}}\left(4-2\cos\frac{\pi i}{m}-2\cos\frac{\pi j}{n}\right).}$

This is the exact formula implemented by all three solution files. The main difficulty is no longer graph theory but numerical scale: the product contains \(mn-1\) positive factors and becomes astronomically large even for moderate \(m\) and \(n\).

Step 4: Why the Code Works in Base-10 Logarithms

Instead of multiplying the eigenvalues directly, the programs sum their base-10 logarithms:

$L=\log_{10} C(m,n)=\sum_{\substack{0 \le i \lt m\\0 \le j \lt n\\ (i,j)\ne(0,0)}}\log_{10}\left(4-2\cos\frac{\pi i}{m}-2\cos\frac{\pi j}{n}\right)-\log_{10}(mn).$

Once \(L\) is known, write

$e=\lfloor L \rfloor,\qquad \mu=10^{L-e},\qquad C(m,n)=\mu \times 10^e,$

where \(1 \le \mu \lt 10\). The code rounds \(\mu\) to five significant digits. If rounding pushes the mantissa to \(10.0000\), it divides by \(10\) and increments the exponent, exactly as the local implementations do.

The C++ version uses Kahan summation for the logarithm sum, which is a small but worthwhile refinement when tens of thousands of floating-point terms are added. The Python and Java versions use the same formula without that extra compensation step.

Worked Checkpoints

The C++ file contains several checkpoints that are useful both mathematically and as implementation tests.

For \(m=n=1\), there is only one vertex and therefore exactly one spanning tree, so \(C(1,1)=1\).

For \(m=n=2\), the nonzero eigenvalues are \(2\), \(2\), and \(4\), hence

$C(2,2)=\frac{2 \cdot 2 \cdot 4}{4}=4.$

The next exact checkpoint used in code is

$C(3,4)=2415,$

and symmetry of the rectangular grid requires \(C(3,4)=C(4,3)\), which the C++ program checks numerically.

For a larger validation point, the code formats

$C(9,12)\approx 2.5720 \times 10^{46},$

and for the actual Project Euler target it prints

$C(100,500)\approx 6.3202 \times 10^{25093}.$

How the Code Works

The C++ solution exposes optional arguments --m=, --n=, and --skip-checkpoints. It precomputes two cosine tables, loops over all \((i,j)\ne(0,0)\), forms the eigenvalue \(4-2c_i-2c_j\), accumulates \(\log_{10}\) with Kahan compensation, subtracts \(\log_{10}(mn)\), and finally reconstructs the scientific notation string. The Python solution follows the same mathematical pipeline and also caches cosine tables, but keeps the code minimal and does not include checkpoints. The Java solution uses the same formula and the same scientific-format rounding rule, but computes the cosine values directly inside the loops instead of storing arrays.

Complexity Analysis

The dominant work is the double loop over the \(mn-1\) nonzero eigenvalue positions, so the running time is \(O(mn)\). The C++ and Python versions store cosine tables of lengths \(m\) and \(n\), so they use \(O(m+n)\) extra memory. The Java translation recomputes cosines and therefore only needs \(O(1)\) extra memory beyond a few scalars. In every version, this is vastly cheaper than forming a giant determinant or performing exact big-integer linear algebra.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=380
2. Matrix-Tree theorem: Wikipedia — Kirchhoff's theorem
3. Laplacian matrix of a graph: Wikipedia — Laplacian matrix
4. Cartesian product of graphs: Wikipedia — Cartesian product of graphs
5. Path graph: Wikipedia — Path graph