Problem 272: Modular Cubes, Part 2

Mathematical Foundation

Theorem 1 (Multiplicativity of Cube-Root Count). Define $c(n) = |\{x \in \{0, 1, \ldots, n-1\} : x^3 \equiv 1 \pmod{n}\}|$. Then $c$ is a multiplicative function: $c(mn) = c(m) \cdot c(n)$ whenever $\gcd(m, n) = 1$.

Proof. By the CRT, $\mathbb{Z}/mn\mathbb{Z} \cong \mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}$ when $\gcd(m,n) = 1$. Under this isomorphism, $x^3 \equiv 1 \pmod{mn}$ iff $x^3 \equiv 1 \pmod{m}$ and $x^3 \equiv 1 \pmod{n}$. The solution set decomposes as a direct product, so $c(mn) = c(m) \cdot c(n)$. $\square$

Lemma 1 (Cube-Root Count for Prime Powers). For a prime $p$ and integer $a \ge 1$:

• $c(2^a) = 1$ for all $a \ge 1$.
• $c(3) = 1$ and $c(3^a) = 3$ for $a \ge 2$.
• $c(p^a) = 3$ for all $a \ge 1$ when $p \equiv 1 \pmod{3}$.
• $c(p^a) = 1$ for all $a \ge 1$ when $p \equiv 2 \pmod{3}$, $p \neq 3$.

Proof. The number of solutions to $x^3 \equiv 1$ in the cyclic group $(\mathbb{Z}/p^a\mathbb{Z})^\times$ of order $\phi(p^a) = p^{a-1}(p-1)$ is $\gcd(3, \phi(p^a))$.

For $p = 2$: $\phi(2^a) = 2^{a-1}$, so $\gcd(3, 2^{a-1}) = 1$.

For $p = 3$: $\phi(3) = 2$, $\gcd(3, 2) = 1$; for $a \ge 2$, $\phi(3^a) = 2 \cdot 3^{a-1}$, $\gcd(3, 2 \cdot 3^{a-1}) = 3$.

For $p \equiv 1 \pmod{3}$: $3 \mid (p-1)$ so $3 \mid \phi(p^a)$, giving $\gcd(3, \phi(p^a)) = 3$.

For $p \equiv 2 \pmod{3}$, $p \neq 3$: $3 \nmid (p-1)$ and $3 \nmid p$, so $\gcd(3, \phi(p^a)) = 1$. $\square$

Theorem 2 (Structure of $c(n)$). For any positive integer $n$, $c(n) = 3^{k(n)}$ where $k(n)$ equals the number of distinct prime divisors $p \equiv 1 \pmod{3}$ of $n$, plus $1$ if $v_3(n) \ge 2$.

Proof. Immediate from Theorem 1 and Lemma 1, since $c(n) = \prod_{p^a \| n} c(p^a)$ and each prime-power factor contributes either $1$ or $3$. $\square$

Corollary (Condition $C(n) = 242$). Since $C(n) = c(n) - 1$, the condition $C(n) = 242$ is equivalent to $c(n) = 243 = 3^5$, i.e., $k(n) = 5$. This splits into two cases:

• Case A: $n$ has exactly 5 distinct prime divisors $\equiv 1 \pmod{3}$, and $9 \nmid n$.
• Case B: $n$ has exactly 4 distinct prime divisors $\equiv 1 \pmod{3}$, and $9 \mid n$.

Lemma 2 (Inclusion—Exclusion Summation). For a fixed “active set” $S$ of primes $\equiv 1 \pmod{3}$ with product $P$, define $L = \lfloor N/P \rfloor$. The sum of all valid multipliers $t \in [1, L]$ having no prime factor $\equiv 1 \pmod{3}$ outside $S$ is:

where $F$ is the set of “forbidden” primes ($\equiv 1 \pmod{3}$, not in $S$, $\le L$), $d_T = \prod_{p \in T} p$, and $f_T = \lfloor L / d_T \rfloor$.

Proof. By the inclusion—exclusion principle applied to the forbidden divisibility conditions. The sum of all multiples of $d$ in $[1, L]$ is $d \cdot f(f+1)/2$ where $f = \lfloor L/d \rfloor$. Alternating signs remove overcounting. $\square$

Editorial

C(n) = c(n) - 1 where c(n) = 3^k, k = number of “active” prime conditions. Need c(n) = 243 = 3^5. Active conditions: Two cases for k = 5: Case A: exactly 5 primes = 1 mod 3, 9 does not divide n Case B: exactly 4 primes = 1 mod 3, 9 divides n. We enumerate primes p ≡ 1 (mod 3) up to N: call them type-A primes. We then case A: Choose 5 type-A primes, 9 does not divide n. Finally, subtract contribution where 9 | t.

Pseudocode

Enumerate primes p ≡ 1 (mod 3) up to N: call them type-A primes
Case A: Choose 5 type-A primes, 9 does not divide n
Subtract contribution where 9 | t
Case B: Choose 4 type-A primes, 9 | n (so factor of 9 is mandatory)

Complexity Analysis

• Time: The DFS over active sets is bounded by the number of subsets of type-A primes whose product does not exceed $N = 10^{11}$. Since the smallest type-A primes are $7, 13, 19, 31, 37, \ldots$ and $7 \cdot 13 \cdot 19 \cdot 31 \cdot 37 = 3{,}233{,}461$, the number of valid 5-subsets is moderate (on the order of $10^5$). The inclusion—exclusion at each leaf prunes aggressively (product of forbidden primes grows exponentially). Overall: $O\!\left(\binom{\pi_A}{5} \cdot 2^{|F|_{\text{eff}}}\right)$ which is practically bounded and runs in under a minute.
• Space: $O(\pi_A)$ for the list of type-A primes, where $\pi_A \approx \pi(10^{11}) / 2$.

Answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 lll;

/*
 * Problem 272: Modular Cubes, Part 2
 *
 * Find the sum of all n <= 10^11 with C(n) = 242 (cube roots of unity minus 1).
 * c(n) = 3^k, need k = 5.
 *
 * Case A: 5 type-A primes (p=1 mod 3), 9 does not divide n.
 * Case B: 4 type-A primes, 9 divides n.
 *
 * Two-phase approach:
 * Phase 1: Enumerate active sets (subsets of type-A primes).
 * Phase 2: For each active set, compute sum of valid n using I-E on forbidden primes.
 */

const ll N = 100000000000LL;

vector<int> typeA;

void sieve(int lim) {
    vector<bool> is_p(lim + 1, true);
    is_p[0] = is_p[1] = false;
    for (int i = 2; i <= lim; i++) {
        if (is_p[i]) {
            if (i >= 7 && i % 3 == 1) typeA.push_back(i);
            for (ll j = (ll)i * i; j <= lim; j += i)
                is_p[j] = false;
        }
    }
}

lll total_sum = 0;

inline lll sum_multiples(ll L, ll d) {
    if (d > L || L <= 0) return 0;
    lll f = L / d;
    return (lll)d * f * (f + 1) / 2;
}

// I-E DFS on forbidden primes
// forbidden: sorted list of type-A primes not in active set, up to L
// Computes sum of t in [1, L] with no forbidden factor (and optional 9-constraint)
void ie_dfs(const vector<int>& forbidden, int idx, ll L, ll prod, int sign,
            ll active_prod, bool caseA, lll& result) {
    // Contribution at this node
    lll contrib;
    if (caseA) {
        contrib = sum_multiples(L, prod);
        if ((lll)prod * 9 <= L) {
            contrib -= sum_multiples(L, prod * 9);
        }
    } else {
        contrib = sum_multiples(L, prod);
    }
    result += (lll)sign * (lll)active_prod * contrib;

    // Recurse
    for (int i = idx; i < (int)forbidden.size(); i++) {
        ll p = forbidden[i];
        if (prod > L / p) break;
        ie_dfs(forbidden, i + 1, L, prod * p, -sign, active_prod, caseA, result);
    }
}

// Enumerate active sets
void active_dfs(int idx, int cnt, int target, ll prod, bool caseA) {
    if (cnt == target) {
        ll L = N / prod;
        if (L < 1) return;

        // Build forbidden list
        vector<int> forbidden;
        // We need all type-A primes up to L that are NOT in the active set.
        // Problem: we don't have the active set stored, just the product.
        // We need to track which primes are active.
        // Let's pass the active set.
        // ... Actually, for the I-E, we just need forbidden primes.
        // Let me restructure to pass active set.
        return;
    }

    for (int i = idx; i < (int)typeA.size(); i++) {
        ll p = typeA[i];
        if (prod > N / p) break;
        active_dfs(i + 1, cnt + 1, target, prod * p, caseA);
    }
}

// Better: pass active set explicitly
void active_dfs2(int idx, int cnt, int target, ll prod, bool caseA,
                  vector<int>& active_set) {
    if (cnt == target) {
        ll L = N / prod;
        if (L < 1) return;

        // Build forbidden: type-A primes not in active_set, up to L
        int ai = 0;
        vector<int> forbidden;
        for (int i = 0; i < (int)typeA.size(); i++) {
            int p = typeA[i];
            if (p > L) break;
            if (ai < (int)active_set.size() && active_set[ai] == p) {
                ai++;
                continue;
            }
            forbidden.push_back(p);
        }

        lll result = 0;
        ie_dfs(forbidden, 0, L, 1, 1, prod, caseA, result);
        total_sum += result;
        return;
    }

    for (int i = idx; i < (int)typeA.size(); i++) {
        ll p = typeA[i];
        if (prod > N / p) break;
        active_set.push_back(typeA[i]);
        active_dfs2(i + 1, cnt + 1, target, prod * p, caseA, active_set);
        active_set.pop_back();
    }
}

void print128(lll v) {
    if (v == 0) { cout << "0" << endl; return; }
    bool neg = false;
    if (v < 0) { neg = true; v = -v; }
    string s;
    while (v > 0) { s += ('0' + (int)(v % 10)); v /= 10; }
    if (neg) s += '-';
    reverse(s.begin(), s.end());
    cout << s << endl;
}

int main() {
    sieve(50000000);

    vector<int> as;

    // Case A: 5 type-A primes, 9 does not divide n
    active_dfs2(0, 0, 5, 1, true, as);

    // Case B: 4 type-A primes, 9 divides n
    active_dfs2(0, 0, 4, 9, false, as);

    print128(total_sum);
    return 0;
}

"""
Problem 272: Modular Cubes, Part 2

Find the sum of all n <= 10^11 with C(n) = 242, where C(n) is the number of
x with 1 < x < n and x^3 = 1 (mod n).

C(n) = c(n) - 1 where c(n) = 3^k, k = number of "active" prime conditions.
Need c(n) = 243 = 3^5.

Active conditions:
- Each distinct prime p = 1 mod 3 dividing n adds 1
- If 9 | n, adds 1

Two cases for k = 5:
Case A: exactly 5 primes = 1 mod 3, 9 does not divide n
Case B: exactly 4 primes = 1 mod 3, 9 divides n
"""

import sys
sys.setrecursionlimit(100000)

N = 10**11

def sieve_primes(lim):
    is_p = bytearray(b'\x01') * (lim + 1)
    is_p[0] = is_p[1] = 0
    for i in range(2, int(lim**0.5) + 1):
        if is_p[i]:
            is_p[i*i::i] = bytearray(len(is_p[i*i::i]))
    return [i for i in range(2, lim + 1) if is_p[i]]

primes = sieve_primes(50000000)
typeA = [p for p in primes if p >= 7 and p % 3 == 1]

total_sum = 0

def sum_multiples(L, d):
    """Sum of multiples of d in [1, L]."""
    if d > L or L <= 0:
        return 0
    f = L // d
    return d * f * (f + 1) // 2

def ie_dfs(forbidden, idx, L, prod, sign, active_prod, case_a):
    """Inclusion-exclusion on forbidden primes."""
    global total_sum
    if case_a:
        contrib = sum_multiples(L, prod)
        if prod * 9 <= L:
            contrib -= sum_multiples(L, prod * 9)
    else:
        contrib = sum_multiples(L, prod)
    total_sum += sign * active_prod * contrib

    for i in range(idx, len(forbidden)):
        p = forbidden[i]
        if prod * p > L:
            break
        ie_dfs(forbidden, i + 1, L, prod * p, -sign, active_prod, case_a)

def active_dfs(idx, cnt, target, prod, case_a, active_set):
    """Enumerate active prime sets."""
    if cnt == target:
        L = N // prod
        if L < 1:
            return
        # Build forbidden list
        ai = 0
        forbidden = []
        for p in typeA:
            if p > L:
                break
            if ai < len(active_set) and active_set[ai] == p:
                ai += 1
                continue
            forbidden.append(p)
        ie_dfs(forbidden, 0, L, 1, 1, prod, case_a)
        return

    for i in range(idx, len(typeA)):
        p = typeA[i]
        if prod * p > N:
            break
        active_set.append(p)
        active_dfs(i + 1, cnt + 1, target, prod * p, case_a, active_set)
        active_set.pop()

def solve():
    global total_sum
    # Case A: 5 type-A primes, no 9|n
    active_dfs(0, 0, 5, 1, True, [])
    # Case B: 4 type-A primes, 9|n
    active_dfs(0, 0, 4, 9, False, [])
    print(total_sum)

if __name__ == "__main__":
    solve()