Detailed mathematical approach

Problem Summary

Let \(\zeta_n=e^{2\pi i/n}\). The quantity \(f(n,m)\) counts the \(m\)-element subsets \(A\subseteq\{0,1,\dots,n-1\}\) for which

$\sum_{j\in A}\zeta_n^j=0.$

Geometrically, we choose \(m\) equally weighted points among the \(n\) equally spaced directions on the unit circle and ask when their vector sum is exactly zero. Directly testing all \(\binom{n}{m}\) subsets is hopeless for the real target, so the implementations reorganize the problem into a smaller primitive cycle and then rebuild the full answer from a generating function.

Mathematical Approach

Write

$S=\operatorname{rad}(n),\qquad G=\frac{n}{S},$

where \(\operatorname{rad}(n)\) is the product of the distinct prime divisors of \(n\). The core fact used by the implementations is that all repeated prime powers can be separated cleanly, so the hard combinatorics happens only on the square-free part \(S\).

Step 1: Encode a Selection by a Polynomial

For a subset \(A\subseteq\{0,\dots,n-1\}\), define the indicator polynomial

$F_A(x)=\sum_{j=0}^{n-1}\varepsilon_j x^j,\qquad \varepsilon_j\in\{0,1\},$

with \(\varepsilon_j=1\) exactly when \(j\in A\). Then \(|A|=\sum \varepsilon_j\), and the zero-sum condition is simply

$F_A(\zeta_n)=0.$

So the problem is not about floating-point geometry at all; it is about deciding when a \(0/1\)-polynomial vanishes at a primitive \(n\)-th root of unity.

Step 2: Split the \(n\)-Cycle into \(G\) Primitive Blocks

Group exponents by their residue modulo \(G\):

$F_A(x)=\sum_{r=0}^{G-1}x^r B_r(x^G),$

where

$B_r(y)=\sum_{q=0}^{S-1}\varepsilon_{r+qG}y^q.$

Because \(\zeta_n^G=\zeta_S\), evaluation at \(\zeta_n\) gives

$F_A(\zeta_n)=\sum_{r=0}^{G-1}\zeta_n^r B_r(\zeta_S).$

Now \(n\) and \(S\) have the same prime divisors, so

$[\mathbb{Q}(\zeta_n):\mathbb{Q}(\zeta_S)]=\frac{\varphi(n)}{\varphi(S)}=\frac{n}{S}=G.$

Therefore \(1,\zeta_n,\zeta_n^2,\dots,\zeta_n^{G-1}\) are linearly independent over \(\mathbb{Q}(\zeta_S)\). The sum above is zero if and only if every block vanishes separately:

$F_A(\zeta_n)=0\iff B_r(\zeta_S)=0\quad\text{for all }r=0,\dots,G-1.$

Each residue class modulo \(G\) is thus an independent rotated copy of an \(S\)-cycle. This is the decisive reduction used by the code.

Step 3: Count Zero-Sum Subsets on One \(S\)-Cycle

Let \(c_k\) be the number of \(k\)-element subsets of \(\{0,\dots,S-1\}\) whose \(S\)-th roots sum to zero. For one such subset \(T\), define

$F_T(x)=\sum_{q\in T}x^q.$

Since \(\zeta_S\) is a primitive \(S\)-th root of unity, its minimal polynomial over \(\mathbb{Q}\) is \(\Phi_S(x)\). Hence

$F_T(\zeta_S)=0\iff \Phi_S(x)\mid F_T(x).$

So the problem becomes: among all \(0/1\)-polynomials of degree \(\lt S\), count how many become the zero element in the quotient ring

$\mathbb{Z}[x]/(\Phi_S(x)).$

The implementations represent each power \(x^q\) by its coefficient vector modulo \(\Phi_S(x)\), whose dimension is \(\varphi(S)\). A subset is valid exactly when those vectors add up to the zero vector.

Step 4: Meet-in-the-Middle for All \(c_k\)

The \(S\) exponents are split into two halves. For each left-half subset, the implementation computes its vector sum in \(\mathbb{Z}[x]/(\Phi_S(x))\), records its size, and stores how many times that vector occurs. Then it enumerates right-half subsets, negates their vector sum, and looks up matches from the left side. If a left subset of size \(a\) and a right subset of size \(b\) have opposite vectors, their union is a zero-sum subset of size \(a+b\).

One meet-in-the-middle pass therefore produces every \(c_k\) for \(0\le k\le m\), not just one cardinality. This is why the later polynomial stage can be exact and inexpensive.

Step 5: Rebuild the Full Count with a Generating Function

For one primitive block define the ordinary generating polynomial

$P_S(t)=\sum_{k=0}^{S}c_k t^k.$

Because the \(G\) residue classes are independent, choosing a valid subset from the full \(n\)-cycle is the same as choosing, for each block, a zero-sum subset on the \(S\)-cycle. Sizes add, so the global generating function is

$P_S(t)^G.$

Therefore

$\boxed{f(n,m)=\left[t^m\right]P_S(t)^G.}$

This boxed formula is exactly what the C++, Python, and Java implementations evaluate.

Worked Example: \(f(12,4)\)

Here \(n=12\), so \(S=\operatorname{rad}(12)=6\) and \(G=12/6=2\). On one 6-cycle, the zero-sum subsets are easy to classify geometrically:

$c_0=1,\qquad c_2=3,\qquad c_3=2,\qquad c_4=3,\qquad c_6=1,$

and all other \(c_k\) are \(0\). Thus

$P_6(t)=1+3t^2+2t^3+3t^4+t^6.$

We only need the coefficient of \(t^4\), so terms above degree \(4\) can be ignored:

$f(12,4)=\left[t^4\right](1+3t^2+2t^3+3t^4)^2.$

The \(t^4\) contribution comes from \(1\cdot 3t^4\), \(3t^4\cdot 1\), and \(3t^2\cdot 3t^2\). Hence

$f(12,4)=3+3+9=15,$

which matches the small checkpoint used by the implementations.

How the Code Works

The implementation first computes \(S=\operatorname{rad}(n)\) and \(G=n/S\). It then builds the cyclotomic polynomial \(\Phi_S(x)\) from the identity \(x^k-1=\prod_{d\mid k}\Phi_d(x)\), reducing powers of \(x\) to coefficient vectors modulo \(\Phi_S(x)\). With those vectors available, it performs the meet-in-the-middle count described above and obtains all coefficients \(c_0,c_1,\dots,c_m\) for one primitive block.

Next it forms the polynomial \(P_S(t)\) and multiplies it by itself \(G\) times, truncating degrees above \(m\) after every multiplication because only \(\left[t^m\right]\) matters. All arithmetic is exact: the Python version relies on native arbitrary-precision integers, the Java version uses arbitrary-precision integer objects, and the C++ version stores large integers explicitly so no modulus ever hides carries or cancellations.

Complexity Analysis

Let \(d=\varphi(S)\). Building and using the quotient-ring representation costs polynomial time in \(S\) and \(d\), which is small compared with the subset search. The meet-in-the-middle stage enumerates about \(2^{S/2}\) subsets on each side and processes vectors of length \(d\), so its practical cost is roughly \(O(2^{S/2}d)\) hash-based work with \(O(2^{S/2})\) stored states. The polynomial stage performs \(G\) truncated convolutions up to degree \(m\), giving \(O(Gm^2)\) exact coefficient operations; the bit-cost depends on the size of the final integer. For the target case \(n=360\), the crucial win is that the hard subset stage depends on \(S=\operatorname{rad}(360)=30\), not on all \(360\) positions.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=768
2. Roots of unity: Wikipedia — Root of unity
3. Cyclotomic polynomials: Wikipedia — Cyclotomic polynomial
4. Generating functions: Wikipedia — Generating function
5. Meet-in-the-middle: Wikipedia — Meet-in-the-middle