Open Source · 7 Languages · 900+ Problems

Project Euler Solutions

Complete solutions in C++, Python & Java — with step-by-step mathematical explanations

All Problems

Problem 272: Modular Cubes, Part 2

Project Euler Problem 272 Solution

EulerSolve provides an optimized solution for Project Euler Problem 272, Modular Cubes, Part 2, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary Let $\rho(n)$ be the number of residues $x \pmod n$ satisfying $x^3\equiv1\pmod n.$ The problem asks for the sum of all integers $n\le10^{11}$ having exactly $242$ nontrivial cube roots of unity. Since the trivial root $x=1$ is always present, this is the same as asking for $\rho(n)=243=3^5.$ Mathematical Approach 1. Root Counts for Prime Powers The whole method starts from $\rho(p^a)$. For a prime $p\neq3$, the unit group modulo $p^a$ has order $\varphi(p^a)=p^{a-1}(p-1).$ The equation $u^3=1$ in a cyclic group has exactly $\gcd(3,\varphi(p^a))$ solutions. Therefore: 1. if $p\equiv2\pmod3$, then $\gcd(3,\varphi(p^a))=1$, so $\rho(p^a)=1$, 2. if $p\equiv1\pmod3$, then $\gcd(3,\varphi(p^a))=3$, so $\rho(p^a)=3$. The prime $p=3$ is special. The code uses the standard fact $\rho(3)=1,\qquad \rho(3^a)=3\quad(a\ge2).$ For example, modulo $9$, the three roots are $1,4,7$. 2. The Entire Root Count Depends Only on “Special” Factors By the Chinese Remainder Theorem, $\rho(n)$ is multiplicative across coprime factors. So if $n=\prod p_i^{a_i},$ then $\rho(n)=\prod \rho(p_i^{a_i}).$ That means the only factors that matter are: 1. distinct primes $p\equiv1\pmod3$, each contributing one factor $3$, regardless of exponent, 2. the prime $3$, but only if its exponent is at least $2$, contributing one factor $3$....

Detailed mathematical approach

Problem Summary

Let $\rho(n)$ be the number of residues $x \pmod n$ satisfying

$x^3\equiv1\pmod n.$

The problem asks for the sum of all integers $n\le10^{11}$ having exactly $242$ nontrivial cube roots of unity. Since the trivial root $x=1$ is always present, this is the same as asking for

$\rho(n)=243=3^5.$

Mathematical Approach

1. Root Counts for Prime Powers

The whole method starts from $\rho(p^a)$.

For a prime $p\neq3$, the unit group modulo $p^a$ has order

$\varphi(p^a)=p^{a-1}(p-1).$

The equation $u^3=1$ in a cyclic group has exactly $\gcd(3,\varphi(p^a))$ solutions. Therefore:

1. if $p\equiv2\pmod3$, then $\gcd(3,\varphi(p^a))=1$, so $\rho(p^a)=1$,

2. if $p\equiv1\pmod3$, then $\gcd(3,\varphi(p^a))=3$, so $\rho(p^a)=3$.

The prime $p=3$ is special. The code uses the standard fact

$\rho(3)=1,\qquad \rho(3^a)=3\quad(a\ge2).$

For example, modulo $9$, the three roots are $1,4,7$.

2. The Entire Root Count Depends Only on “Special” Factors

By the Chinese Remainder Theorem, $\rho(n)$ is multiplicative across coprime factors. So if

$n=\prod p_i^{a_i},$

then

$\rho(n)=\prod \rho(p_i^{a_i}).$

That means the only factors that matter are:

1. distinct primes $p\equiv1\pmod3$, each contributing one factor $3$, regardless of exponent,

2. the prime $3$, but only if its exponent is at least $2$, contributing one factor $3$.

The code encodes this with

$\rho(n)=3^{s(n)},\qquad s(n)=\omega_1(n)+\mathbf 1_{v_3(n)\ge2},$

where $\omega_1(n)$ counts distinct prime divisors congruent to $1\pmod3$.

3. Target Condition $\rho(n)=243$

Because $243=3^5$, we need

$s(n)=5.$

This splits the search into two disjoint cases:

1. Case A: exactly five distinct primes $p\equiv1\pmod3$, and $v_3(n)<2$,

2. Case B: exactly four such primes, and $v_3(n)\ge2$.

Those are the only possibilities, because every special contributor adds exactly one factor $3$ to $\rho(n)$.

4. What the Remaining Cofactor Is Allowed to Contain

Once the special contributors have been fixed, the rest of $n$ must not create any new factor $3$ in $\rho(n)$.

So the remaining cofactor may contain only primes $q\equiv2\pmod3$, because such primes contribute $\rho(q^a)=1$.

There is one extra detail:

1. in Case A, a single factor $3$ is allowed, since $v_3(n)=1$ still contributes nothing extra,

2. in Case B, no additional factor $3$ may appear in the cofactor, because the $3^a$ contribution is already handled explicitly by taking $a\ge2$.

5. Why the Search Uses Prime Powers, Not Just Primes

A prime $p\equiv1\pmod3$ contributes the same factor $3$ to $\rho(n)$ no matter whether it appears as $p$, $p^2$, or $p^{17}$. Therefore the DFS must enumerate prime powers, not merely distinct primes.

The same phenomenon occurs for $3$: once the exponent reaches $2$, every larger power $3^a$ still contributes only one factor $3$ to $\rho(n)$.

This is exactly why the recursion loops over

$p,\;p^2,\;p^3,\dots$

as long as the global product remains within the limit.

6. Prefix Sums for the “Ordinary” Cofactor

The code precomputes the function

$F(M)=\sum_{\substack{m\le M\\ p\mid m\Rightarrow p\equiv2\pmod3}} m,$

the sum of all integers up to $M$ whose prime factors are all $2\pmod3$.

This is stored as a prefix table prefix_allowed_sum_.

Then:

1. in Case B, the terminal contribution is just $F(M)$,

2. in Case A, the cofactor may also include one extra factor $3$, so the code uses

$F(M)+3F(\lfloor M/3\rfloor).$

That makes each leaf contribution $O(1)$.

7. DFS Structure and Pruning

The search explores only primes $p\equiv1\pmod3$. To avoid useless branches, the code precomputes min_prod_[r][i], the smallest possible product of $r$ future special primes starting from index $i$.

If even that minimal remaining product already exceeds the limit, the branch is abandoned immediately. This pruning is the reason the search is practical up to $10^{11}$.

8. Worked Structural Examples

A number like

$n=7\cdot13\cdot19\cdot31\cdot37$

has exactly five special $1\pmod3$ primes and no $3^2$, so $\rho(n)=3^5=243$ and it belongs to Case A.

A number like

$n=9\cdot7\cdot13\cdot19\cdot31$

has four special $1\pmod3$ primes plus $v_3(n)\ge2$, so again $\rho(n)=3^5=243$; this is Case B.

In contrast, multiplying either example by a new prime such as $43\equiv1\pmod3$ would push the root count to $3^6$, which is too large.

9. Validation Logic in the Code

The program checks three things before solving the full problem:

1. it verifies that modulo $91$ there are exactly $9$ cube roots of unity, so the nontrivial count is $8$,

2. for every $n\le2000$, it compares the formula-based root count against a brute-force count of solutions to $x^3\equiv1\pmod n$,

3. up to $5{,}000{,}000$, it compares the fast summation algorithm with a brute-force sum over all $n$ having $s(n)=5$.

These checkpoints validate both the arithmetic formula and the large-scale enumeration strategy.

How the Code Works

special_factor_count computes $s(n)$, the exponent of $3$ in $\rho(n)$.

build_special_primes generates all primes $p\equiv1\pmod3$ that could possibly appear in a valid solution under the $10^{11}$ limit.

build_cofactor_prefix precomputes the prefix sums for cofactors made only of primes $2\pmod3$.

solve_case_without_9 handles Case A, and solve_case_with_9 handles Case B.

Each case uses DFS over special prime powers and aggregates whole blocks of remaining cofactors in constant time via the prefix table.

Complexity Analysis

The algorithm is dominated by the number of reachable DFS nodes after pruning. That search space is vastly smaller than the naive set of all integers up to $10^{11}$.

Terminal aggregation is $O(1)$ because the cofactor sums are precomputed. So, in practice, the runtime is determined almost entirely by the number of viable special-factor branches.