Problem 937: Equiproduct Partition
View on Project EulerProject Euler Problem 937 Solution
EulerSolve provides an optimized solution for Project Euler Problem 937, Equiproduct Partition, with C++, Python, Java, and a step-by-step mathematical explanation.
Problem Summary Problem 937 asks us to sum those factorials \(k!\) that satisfy the equiproduct-partition condition from the statement, with the final result taken modulo \(10^9+7\). The implementations never search for partitions directly. Instead, they rely on a theorem that converts the condition for \(k!\) into a parity test built from the prime exponents of \(k!\). So the computational problem is: for every \(1 \le k \le n\), evaluate that arithmetic test quickly, keep track of \(k! \bmod 10^9+7\), and add the current factorial exactly when the equiproduct criterion is true. Mathematical Approach The difficult combinatorial part of the problem is already distilled into one number-theoretic characterization. The remaining job is to evaluate that characterization for every \(k\) without recomputing the full factorization of each factorial from scratch. The criterion used by the solver Let \[ \mathcal P=\{p \le n : p \equiv 2,5,7 \pmod 8\}. \] For each prime \(p\in\mathcal P\), define \[ e_p(k)=v_p(k!), \] where \(v_p\) is the usual \(p\)-adic valuation. Also let \(s_2(m)\) denote the sum of the binary digits of \(m\), and set \[ t(m)=s_2(m)\bmod 2. \] The implementations use the characterization \[ I(k)=\sum_{p\in\mathcal P} t(e_p(k)) \pmod 2. \] The factorial \(k!\) contributes to the answer if and only if \(I(k)=0\)....
Detailed mathematical approach
Problem Summary
Problem 937 asks us to sum those factorials \(k!\) that satisfy the equiproduct-partition condition from the statement, with the final result taken modulo \(10^9+7\). The implementations never search for partitions directly. Instead, they rely on a theorem that converts the condition for \(k!\) into a parity test built from the prime exponents of \(k!\).
So the computational problem is: for every \(1 \le k \le n\), evaluate that arithmetic test quickly, keep track of \(k! \bmod 10^9+7\), and add the current factorial exactly when the equiproduct criterion is true.
Mathematical Approach
The difficult combinatorial part of the problem is already distilled into one number-theoretic characterization. The remaining job is to evaluate that characterization for every \(k\) without recomputing the full factorization of each factorial from scratch.
The criterion used by the solver
Let
\[ \mathcal P=\{p \le n : p \equiv 2,5,7 \pmod 8\}. \]
For each prime \(p\in\mathcal P\), define
\[ e_p(k)=v_p(k!), \]
where \(v_p\) is the usual \(p\)-adic valuation. Also let \(s_2(m)\) denote the sum of the binary digits of \(m\), and set
\[ t(m)=s_2(m)\bmod 2. \]
The implementations use the characterization
\[ I(k)=\sum_{p\in\mathcal P} t(e_p(k)) \pmod 2. \]
The factorial \(k!\) contributes to the answer if and only if \(I(k)=0\).
The crucial subtlety is that the code is not taking the parity of \(e_p(k)\) itself. It is taking the parity of the number of 1-bits in the binary expansion of \(e_p(k)\). That is exactly why the implementation uses a bit-parity primitive instead of a simple odd/even test.
The residue classes \(2,5,7 \pmod 8\) are therefore not a heuristic. They are the precise prime classes singled out by the equiproduct criterion behind the solver.
From Legendre's formula to an incremental update
For a fixed prime \(p\), the exponent of \(p\) in \(k!\) is given by Legendre's formula:
\[ e_p(k)=\sum_{a\ge 1}\left\lfloor \frac{k}{p^a}\right\rfloor. \]
Evaluating this independently for every pair \((p,k)\) would be far too slow. The useful observation is that \(e_p(k)\) changes only when \(k\) is divisible by \(p\). If \(q\) is a multiple of \(p\), then
\[ e_p(q)=e_p(q-1)+v_p(q), \]
while for nonmultiples we simply have \(e_p(k)=e_p(k-1)\).
That means each prime can be processed by scanning only
\[ p,2p,3p,\dots \]
and maintaining the current value of \(e_p(k)\). The inner divisions in the code do nothing mysterious: they are just extracting \(v_p(q)\) when \(q\) contains higher powers of \(p\).
Why a difference array is enough
For each selected prime, define the bit
\[ B_p(k)=t(e_p(k)). \]
The global equiproduct indicator is the xor, or equivalently the sum modulo 2, of all these bits. Instead of storing the full table of every \(B_p(k)\), the implementation stores only the places where a prime contribution changes:
\[ \Delta_p(k)=B_p(k)\oplus B_p(k-1). \]
Because \(B_p(k)\) can change only at multiples of \(p\), \(\Delta_p(k)\) is sparse. The shared array `diff` accumulates
\[ \Delta(k)=\bigoplus_{p\in\mathcal P}\Delta_p(k). \]
Once that array has been built, the true state is reconstructed by one prefix xor:
\[ I(k)=I(k-1)\oplus \Delta(k). \]
This is the central invariant of the whole method. The solver never recomputes the full criterion for a given \(k\); it only tracks when the criterion flips.
Worked example: why \(6!\) is counted but \(7!\) is not
Up to \(7\), the relevant primes are \(2,5,7\). For \(k=6\) we have
\[ v_2(6!)=4,\qquad v_5(6!)=1,\qquad v_7(6!)=0. \]
Now compute the binary-digit parities:
\[ t(4)=s_2(4)\bmod 2=1,\qquad t(1)=1,\qquad t(0)=0. \]
Therefore
\[ I(6)=1+1+0\equiv 0 \pmod 2, \]
so \(6!=720\) is added to the answer.
Passing from \(6!\) to \(7!\) changes only the exponent of prime \(7\): now \(v_7(7!)=1\), hence \(t(v_7(7!))=1\). So the global state flips once:
\[ I(7)=I(6)\oplus 1=1. \]
Thus \(7!\) does not contribute. This matches the checkpoint values: up to \(7\), the contributing factorials are \(1!\), \(4!\), and \(6!\).
Final summation
While the prefix xor reconstructs \(I(k)\), the implementation also maintains
\[ F(k)\equiv k! \pmod{10^9+7} \]
through the recurrence
\[ F(k)=k\cdot F(k-1)\pmod{10^9+7}. \]
Whenever \(I(k)=0\), the current value \(F(k)\) is added to the running total. No factorial is factored separately, and no partition object is generated explicitly.
How the Code Works
Sieve and prime-event pass
The C++ and Java implementations begin with a standard sieve of Eratosthenes up to \(n\). They discard primes congruent to \(1\) or \(3\) modulo \(8\), because those primes never affect the equiproduct criterion encoded by the solver. For every remaining prime, they walk through its multiples, update the running factorial exponent for that prime, compare the old and new values of \(t(e)\), and xor the resulting flip into one shared byte array.
This is why the code needs only one running exponent per prime and one global difference array. It never materializes all values of \(v_p(k!)\) for all \(p\) and \(k\).
Final scan and cross-language structure
After all prime events have been merged into the difference array, one left-to-right pass finishes the job. The implementation keeps a running xor for the equiproduct indicator and a running factorial modulo \(10^9+7\). Whenever the indicator is zero, it adds the current factorial to the answer.
The C++ and Java implementations perform this arithmetic directly. The provided Python entry point is a thin wrapper around the same compiled computation, so all three delivered implementations are driven by the same mathematical test and the same final accumulation rule.
Complexity Analysis
The sieve costs \(O(n \log \log n)\). The main multiple-scan work is
\[ \sum_{p\in\mathcal P}\left\lfloor \frac{n}{p}\right\rfloor, \]
and the extra divisions needed to detect higher prime powers contribute
\[ \sum_{p\le n}\sum_{a\ge 2}\left\lfloor \frac{n}{p^a}\right\rfloor. \]
The first sum is \(O(n\log\log n)\), and the second is \(O(n)\), so the preprocessing remains \(O(n\log\log n)\) overall.
The final prefix-xor and factorial sweep is \(O(n)\). Memory usage is \(O(n)\), dominated by the difference array and the sieve storage.