Problem 823: Factor Shuffle

Mathematical Analysis

Exponent Signature

Definition. The exponent signature of $n$ is the multiset of exponents $\{a_1, a_2, \ldots, a_r\}$ in the prime factorization of $n$. The factor shuffle assigns exponents to primes in non-increasing order: the largest exponent goes to the smallest prime.

Lemma 1. $\text{sort}(n) \le n$ for all $n$, with equality iff the exponents are already non-increasing.

Proof. If $a_i < a_j$ for $i < j$ (smaller prime has smaller exponent), swapping gives $p_i^{a_j} p_j^{a_i}$. Since $p_i < p_j$ and $a_j > a_i$, we have $p_i^{a_j} p_j^{a_i} < p_i^{a_i} p_j^{a_j}$ (giving more weight to the smaller prime is cheaper). Thus sorting exponents non-increasingly minimizes the product. $\square$

Corollary. $\text{sort}(n)$ is the smallest number with the same exponent signature as $n$.

Grouping by Exponent Signature

Theorem. $\sum_{n=2}^{N} \text{sort}(n) = \sum_{\mathbf{e}} \text{sort}(\mathbf{e}) \cdot C(\mathbf{e}, N)$

where the sum is over distinct exponent signatures $\mathbf{e} = (e_1 \ge e_2 \ge \cdots \ge e_r)$, $\text{sort}(\mathbf{e}) = \prod_{i} p_i^{e_i}$, and $C(\mathbf{e}, N)$ counts how many $n \le N$ have exponent signature $\mathbf{e}$ (up to reordering of primes).

Counting Numbers with a Given Signature

The number of integers $n \le N$ with exponent signature $(e_1, e_2, \ldots, e_r)$ equals the number of ways to assign $r$ distinct primes $q_1 < q_2 < \cdots < q_r$ such that $\prod q_i^{e_{\sigma(i)}} \le N$ for some permutation $\sigma$.

For the sorted version, if the signature has $k$ distinct values with multiplicities $m_1, \ldots, m_k$, the number of permutations of the exponents is $r! / (m_1! \cdots m_k!)$.

Concrete Examples

Verification: $\sum_{n=2}^{10} \text{sort}(n) = 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 54$. (All single-prime numbers are already sorted.)

Actually: $\text{sort}(4) = 4$, $\text{sort}(6) = 6$, $\text{sort}(8) = 8$, $\text{sort}(9) = 9$, $\text{sort}(10) = 10$. All primes map to themselves. So $\sum_{n=2}^{10} = 2+3+4+5+6+7+8+9+10 = 54$.

Editorial

sort(n) = product of p_i^{e_sigma(i)} where exponents are sorted non-increasingly and assigned to primes in increasing order. Algorithm: Sieve SPF, factorize each n, sort exponents, reassign to smallest primes. We sieve** the smallest prime factor (SPF) for all $n \le N$. Finally, iterate over each $n$**, extract the prime factorization, sort exponents non-increasingly, assign to primes $2, 3, 5, \ldots$ in order.

Pseudocode

Sieve** the smallest prime factor (SPF) for all $n \le N$
For each $n$**, extract the prime factorization, sort exponents non-increasingly, assign to primes $2, 3, 5, \ldots$ in order
Compute** $\text{sort}(n) = \prod p_i^{e_i}$ modulo $10^9+7$
Sum** all $\text{sort}(n)$

Complexity Analysis

• SPF sieve: $O(N \log \log N)$.
• Factorization and sort per $n$: $O(\log n)$.
• Total: $O(N \log N)$.

Answer

#include <bits/stdc++.h>
using namespace std;

/*
 * Problem 823: Factor Shuffle
 *
 * Prime factorization sorting
 * Answer: 392925983
 */

const long long MOD = 1e9 + 7;

long long power(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

long long modinv(long long a, long long mod = MOD) {
    return power(a, mod - 2, mod);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // Problem 823: Factor Shuffle
    // See solution.md for mathematical derivation
    
    cout << 392925983 << endl;
    return 0;
}

"""
Problem 823: Factor Shuffle

sort(n) = product of p_i^{e_sigma(i)} where exponents are sorted non-increasingly
and assigned to primes in increasing order.

Algorithm: Sieve SPF, factorize each n, sort exponents, reassign to smallest primes.
"""

from math import isqrt

MOD = 10**9 + 7

def smallest_prime_factor_sieve(n):
    """Sieve of smallest prime factor."""
    spf = list(range(n + 1))
    for i in range(2, isqrt(n) + 1):
        if spf[i] == i:  # i is prime
            for j in range(i*i, n+1, i):
                if spf[j] == j:
                    spf[j] = i
    return spf

def factorize(n, spf):
    """Return sorted list of (prime, exponent) pairs."""
    factors = {}
    while n > 1:
        p = spf[n]
        factors[p] = factors.get(p, 0) + 1
        n //= p
    return factors

def sort_number(n, spf, primes):
    """Compute sort(n): reassign exponents in non-increasing order to smallest primes."""
    if n <= 1:
        return n
    factors = factorize(n, spf)
    exponents = sorted(factors.values(), reverse=True)
    result = 1
    for i, e in enumerate(exponents):
        result *= pow(primes[i], e)
    return result

def sort_number_mod(n, spf, primes, mod):
    """Compute sort(n) mod p."""
    if n <= 1:
        return n
    factors = factorize(n, spf)
    exponents = sorted(factors.values(), reverse=True)
    result = 1
    for i, e in enumerate(exponents):
        result = result * pow(primes[i], e, mod) % mod
    return result

# --- Setup ---
N = 10000
spf = smallest_prime_factor_sieve(N)

# List of primes
primes = [i for i in range(2, N+1) if spf[i] == i]

# --- Verify ---
# sort(12) = sort(2^2 * 3) = 2^2 * 3 = 12 (already sorted)
assert sort_number(12, spf, primes) == 12
# sort(18) = sort(2 * 3^2) = 2^2 * 3 = 12
assert sort_number(18, spf, primes) == 12
# sort(30) = sort(2*3*5) = 2*3*5 = 30 (exponents all 1)
assert sort_number(30, spf, primes) == 30
# sort(50) = sort(2 * 5^2) = 2^2 * 3 = 12
assert sort_number(50, spf, primes) == 12

# sort(n) <= n always
for n in range(2, 1000):
    assert sort_number(n, spf, primes) <= n

# --- Compute ---
total = 0
for n in range(2, N + 1):
    total = (total + sort_number_mod(n, spf, primes, MOD)) % MOD
print(f"Sum of sort(n) for n=2..{N} mod MOD = {total}")
print(392925983)