Detailed mathematical approach

Problem Summary

Problem 995 looks like a question about divisibility of two sparse polynomials, but the useful object is not a polynomial expansion. For a prime \(p\), \(f_p(x)=1+x+\cdots+x^{p-1}\) is the cyclotomic polynomial \(\Phi_p(x)\). Therefore divisibility by \(f_p\) can be tested at a primitive \(p\)-th root of unity. This turns the problem into a question about how the divisor set of an integer \(s\) is distributed among residue classes modulo \(p\).

The main reduction is that \(f_p(x)\mid g_s(x)\) holds exactly when the positive divisors of \(s\) form a perfect tiling of \(\mathbb{F}_p^\times\) by residues. Consequently \(p\nmid s\), \(\tau(s)=p-1\), and each non-zero residue class modulo \(p\) must be hit exactly once by a divisor of \(s\). The implementation then searches for the numerically smallest such \(s\), not by enumerating divisors of candidate integers, but by building a subgroup chain inside the cyclic group \(\mathbb{F}_p^\times\).

The final product \(T(20000)\) is much too large to store. The program computes each \(\log_{10} S(p)\), sums those logarithms over all primes \(p\lt 20000\), and formats the final mantissa and exponent. Exact integer reconstruction is used only for small validation cases such as \(S(5)=8\), \(T(20)=1348422598656\), and the stated \(T(100)\) checkpoint.

Mathematical Approach and Notation

For a prime \(p\) and a positive integer \(n\), the problem defines

$f_p(x)=\sum_{i=0}^{p-1}x^i,\qquad g_n(x)=1+\sum_{d\mid n}x^d.$

The term \(1\) in \(g_n\) is important: it is an extra constant term whose exponent is \(0\). The divisors \(d\mid n\) are positive divisors and contribute exponents \(d\). We seek the least positive integer \(s\) such that \(f_p(x)\mid g_s(x)\), denoted \(S(p)\).

Throughout the analysis, \(G=\mathbb{F}_p^\times\) denotes the multiplicative group of non-zero residues modulo \(p\). This group is cyclic of order \(p-1\). If \(g\) is a primitive root modulo \(p\), every non-zero residue has a unique representation \(g^e\), \(0\le e\lt p-1\); the exponent \(e\) is the discrete logarithm used by the code.

Lemma 1: The Cyclotomic Root Condition

Let \(\zeta\ne 1\) be a primitive \(p\)-th root of unity. Since \(p\) is prime,

$f_p(x)=1+x+\cdots+x^{p-1}=\Phi_p(x),$

and \(\Phi_p(x)\) is the minimal polynomial of \(\zeta\) over \(\mathbb{Q}\). Therefore \(f_p(x)\mid g_s(x)\) if and only if \(g_s(\zeta)=0\).

Group the exponents of \(g_s\) by their residue classes modulo \(p\). Let \(c_r\) be the number of terms in \(g_s\) whose exponent is congruent to \(r\pmod p\). Then

$g_s(\zeta)=\sum_{r=0}^{p-1}c_r\zeta^r.$

The powers \(1,\zeta,\ldots,\zeta^{p-1}\) satisfy one rational linear relation, namely \(1+\zeta+\cdots+\zeta^{p-1}=0\), and all rational relations are multiples of it. Hence \(g_s(\zeta)=0\) is equivalent to

$c_0=c_1=\cdots=c_{p-1}.$

Thus the polynomial divisibility problem has become a balancing condition on residue-class counts. The coefficients of the polynomials themselves never need to be expanded.

Lemma 2: The Divisors of \(s\) Tile \(\mathbb{F}_p^\times\)

First suppose \(p\mid s\), and write \(s=p^a u\), with \(a\ge 1\) and \(p\nmid u\). The divisors not divisible by \(p\) are exactly the divisors of \(u\), so all non-zero residue classes together receive \(\tau(u)\) contributions. If the common residue count is \(C\), then

$\tau(u)=(p-1)C.$

The zero residue class receives the extra constant term and every divisor containing at least one factor \(p\), so its count is \(1+a\tau(u)\). Equality of all \(c_r\) would require

$C=1+a\tau(u)=1+a(p-1)C,$

which is impossible for positive \(C\). Hence no valid minimal or non-minimal solution can have \(p\mid s\).

Now \(p\nmid s\). Every divisor of \(s\) is non-zero modulo \(p\), and the only contribution to residue class \(0\) is the separate constant term in \(g_s\). Therefore \(c_0=1\). Since all \(c_r\) must be equal, every non-zero class must also occur exactly once. The divisibility condition is therefore equivalent to the bijection

$\{d:d\mid s\}\longrightarrow \mathbb{F}_p^\times,\qquad d\longmapsto d\bmod p.$

In particular, the number of divisors must be

$\tau(s)=p-1.$

Subgroup-Chain Model

Write the unknown integer in prime-power form

$s=\prod_{j=1}^k q_j^{a_j},\qquad q_j\ne p,$

and define the divisor-box lengths \(\ell_j=a_j+1\). Since \(\tau(s)=\prod_j(a_j+1)\), the lengths must satisfy

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

Choosing a factor \(q_j^{a_j}\) adds the finite progression \(1,q_j,q_j^2,\ldots,q_j^{\ell_j-1}\) to the divisor box. Modulo \(p\), these progressions should multiply together without collisions and eventually cover the whole cyclic group \(G\). The implementation uses the canonical subgroup-chain formulation of this condition: after some steps the already constructed residues are the unique subgroup \(H\le G\) of size \(h\mid p-1\).

Assume the current subgroup has size \(h\). The quotient group \(G/H\) has order

$Q={p-1\over h}.$

A new prime residue \(q\) may be used with length \(\ell\mid Q\) precisely when the coset \(qH\) has order \(\ell\) in \(G/H\). Then the cosets

$H,\;qH,\;q^2H,\;\ldots,\;q^{\ell-1}H$

are distinct, and multiplying the old subgroup by \(1,q,\ldots,q^{\ell-1}\) gives the unique subgroup of size \(h\ell\). This is exactly the no-collision condition needed by the divisor tiling.

Using a primitive root \(g\), write \(q\equiv g^e\pmod p\). In the quotient of order \(Q\), the order of \(qH\) is

$\operatorname{ord}_{G/H}(qH)={Q\over \gcd(e,Q)}.$

Therefore the transition condition used in the solver is

$\operatorname{ord}_{G/H}(qH)=\ell \quad\Longleftrightarrow\quad \gcd(e,Q)={Q\over \ell}.$

Optimization as Dynamic Programming

The value of \(s\) should be minimal as an integer. If a transition uses a prime \(q\) with length \(\ell\), then it contributes the factor \(q^{\ell-1}\) to \(s\). The code minimizes logarithms, so the transition weight is

$w(\ell,q)=(\ell-1)\log_{10}q.$

For a fixed state \(h\) and a fixed length \(\ell\), the future state depends only on \(h\ell\), not on the path by which \(h\) was reached. Because \(G\) is cyclic, there is a unique subgroup of each size \(h\mid p-1\). Hence the best prime for that transition is simply the smallest prime \(q\ne p\) satisfying the discrete-log condition above.

The dynamic program stores \(D(h)\), the smallest known value of \(\log_{10}\) of the partial integer that constructs the subgroup of size \(h\). It starts with

$D(1)=0,$

and for every divisor \(\ell\gt 1\) of \(Q=(p-1)/h\), it relaxes

$D(h\ell)=\min\left(D(h\ell),\;D(h)+(\ell-1)\log_{10}q\right),$

where \(q\) is the smallest transition prime with \(\gcd(\log_g q,Q)=Q/\ell\). The answer for one prime is \(D(p-1)=\log_{10}S(p)\). Parent pointers record the chosen pairs \((\ell,q)\), which lets the program reconstruct exact small values for validation.

Correctness Argument

The root-condition lemma proves that polynomial divisibility is equivalent to equal residue counts. The divisor-tiling lemma then proves that any solution must have \(p\nmid s\) and that its divisors must hit the elements of \(G\) exactly once. Thus solving the original problem is equivalent to finding the smallest integer whose divisor box is a collision-free product decomposition of \(G\).

Each DP transition is valid because the quotient-order condition makes the new powers \(1,q,\ldots,q^{\ell-1}\) represent \(\ell\) distinct cosets of the current subgroup. The old subgroup has \(h\) elements, so the enlarged product has \(h\ell\) distinct residues and is exactly the subgroup of that size. By induction, every DP path from \(1\) to \(p-1\) constructs a valid divisor tiling and hence a valid integer \(s\).

Conversely, in the cyclic group setting relevant here, an exact divisor-box tiling can be read as a sequence of quotient complements: at each stage one chooses a divisor-box direction whose images are distinct cosets over the subgroup already constructed. Since the group has only one subgroup of each divisor size, the state \(h\) loses no subgroup identity information. Therefore the DP considers the necessary canonical transitions, and taking the minimum over them yields \(S(p)\).

Worked Examples and Checkpoints

For \(p=2\), \(f_2(x)=1+x\), and \(g_1(x)=1+x\), so \(S(2)=1\). This is the degenerate group case \(G=\mathbb{F}_2^\times\), whose order is \(1\); the DP starts and finishes at the same state.

For \(p=5\), \(G\) has order \(4\). The smallest primitive residue is \(2\). A single transition with \(\ell=4\) gives

$S(5)=2^{4-1}=8,$

matching the problem statement. Its divisors \(1,2,4,8\) reduce modulo \(5\) to \(1,2,4,3\), all non-zero residues exactly once.

For \(p=7\), the optimal chain can be expressed as \((\ell,q)=(3,2)\) followed by \((2,3)\). The resulting integer is

$S(7)=2^{3-1}3^{2-1}=12.$

The divisors \(1,2,4,3,6,12\) reduce modulo \(7\) to \(1,2,4,3,6,5\), again a complete tiling of \(\mathbb{F}_7^\times\). The full implementation checks these local examples and also verifies the product checkpoints \(T(20)=1348422598656\) and \(T(100)=1.37451\mathrm{e}123\).

Implementation Details

The C++, Python, and Java versions follow the same pipeline. They sieve primes up to \(2\,000\,000\), factor \(p-1\), enumerate all divisors of \(p-1\), find a primitive root modulo \(p\), and build a discrete-log table mapping each non-zero residue to its exponent with respect to that root.

The function that searches a transition prime scans the precomputed prime list and rejects \(q=p\). If no suitable prime appears inside the sieve range, the implementation continues by trial primality testing beyond the sieve. In practice the bound is generous for the \(p\lt 20000\) instances, but the fallback keeps the logic complete rather than dependent on a guessed cutoff.

All large products are handled logarithmically. Exact multiplication is retained only for reconstructed small \(S(p)\) values and for \(T(20)\). This separation is important: the final \(T(20000)\) has hundreds of thousands of decimal digits, while its scientific notation only needs the fractional part and integer part of the summed base-10 logarithm.

Complexity and Numerical Stability

For a single prime \(p\), the DP state count is \(\tau(p-1)\), the number of divisors of \(p-1\). Each state tests divisor lengths \(\ell\mid (p-1)/h\), and each transition scans primes until it finds a residue with the required quotient order. The memory use for the discrete-log table is \(O(p)\), and it is discarded after that prime is solved.

The full target has only \(2262\) primes below \(20000\). The algorithm therefore spends its time on small divisor lattices of \(p-1\), not on polynomial coefficients and not on divisors of a gigantic candidate integer. Long-double logarithms are sufficient because the output requires a rounded mantissa with five digits after the decimal point; the exact small checkpoints guard against structural errors in the reduction.

References

1. Problem page: Project Euler 995
2. Cyclotomic polynomial: Wikipedia - Cyclotomic polynomial
3. Finite field: Wikipedia - Finite field
4. Primitive root modulo \(n\): Wikipedia - Primitive root modulo n
5. Dynamic programming: Wikipedia - Dynamic programming