Problem 622: Riffle Shuffles

Mathematical Analysis

Connection to Multiplicative Order

The shuffle permutation sends position $i$ to $2i \bmod (2n+1)$. After $k$ shuffles, position $i$ goes to $2^k i \bmod (2n+1)$. The deck returns to its original order when $2^k \equiv 1 \pmod{2n+1}$ for all $i$, which happens at $k = \text{ord}_{2n+1}(2)$.

Reformulation

Setting $m = 2n+1$, we seek all odd $m > 1$ with $\text{ord}_m(2) = 60$. The deck size is $m - 1$ and we sum all such values:

Factorization of $2^{60} - 1$

The condition $\text{ord}_m(2) = 60$ requires $m \mid 2^{60} - 1$. The complete factorization is:

This has $(2+1)(2+1)(1+1)^8 = 2304$ divisors.

Verifying Exact Order

For a divisor $m$ of $2^{60}-1$, we already know $2^{60} \equiv 1 \pmod{m}$. The order is exactly 60 if and only if $2^{60/p} \not\equiv 1 \pmod{m}$ for every prime $p \mid 60$.

Since $60 = 2^2 \cdot 3 \cdot 5$, the prime divisors are $\{2, 3, 5\}$, and we check:

Connection to Cyclotomic Polynomials

The prime factorization of $2^{60}-1$ decomposes via cyclotomic polynomials:

Every prime $p \mid \Phi_d(2)$ has $\text{ord}_p(2) = d$. So the primes with order exactly 60 are precisely those dividing $\Phi_{60}(2)$.

Composite Orders via CRT

For composite $m = m_1 m_2$ with $\gcd(m_1, m_2) = 1$:

This means composite $m$ with order 60 arise by combining prime powers whose individual orders have $\text{lcm} = 60$. Since $60 = 2^2 \cdot 3 \cdot 5$, valid combinations use primes whose orders divide 60 and whose lcm equals 60.

Concrete Examples of Shuffle Orders

Note: $m = 15 = 3 \cdot 5$, $\text{ord}_{15}(2) = \text{lcm}(\text{ord}_3(2), \text{ord}_5(2)) = \text{lcm}(2, 4) = 4$.

Derivation

Editorial

A perfect (out-)riffle shuffle on 2n cards has order ord_{2n+1}(2). Find sum of deck sizes 2n where the shuffle order is exactly 60. Key identity: ord_m(2) = 60 iff m | 2^60 - 1 and 2^{60/p} != 1 mod m for each prime p | 60 (i.e., p in {2, 3, 5}). 2^60 - 1 = 3^2 * 5^2 * 7 * 11 * 13 * 31 * 41 * 61 * 151 * 331 * 1321 Method 1: Enumerate all divisors, check order (primary) Method 2: Compute ord_m(2) directly for small m (verification). We factorize** $2^{60} - 1$ into prime powers: $3^2 \cdot 5^2 \cdot 7 \cdot 11 \cdot 13 \cdot 31 \cdot 41 \cdot 61 \cdot 151 \cdot 331 \cdot 1321$. We then enumerate** all 2304 divisors $m > 1$ using Cartesian product of exponent ranges. Finally, filter**: for each $m$, verify $2^{30} \not\equiv 1$, $2^{20} \not\equiv 1$, $2^{12} \not\equiv 1 \pmod{m}$.

Pseudocode

Factorize** $2^{60} - 1$ into prime powers: $3^2 \cdot 5^2 \cdot 7 \cdot 11 \cdot 13 \cdot 31 \cdot 41 \cdot 61 \cdot 151 \cdot 331 \cdot 1321$
Enumerate** all 2304 divisors $m > 1$ using Cartesian product of exponent ranges
Filter**: for each $m$, verify $2^{30} \not\equiv 1$, $2^{20} \not\equiv 1$, $2^{12} \not\equiv 1 \pmod{m}$
Sum** $m - 1$ for each valid $m$

Verification

• $m = 1321$: $2^{30} \bmod 1321 = 1320 \ne 1$. Valid.
• $m = 7$: $\text{ord}_7(2) = 3$, so $2^{12} \equiv (2^3)^4 \equiv 1 \pmod{7}$. Invalid.
• $m = 3 \cdot 5 \cdot 7 = 105$: $\text{ord}_{105}(2) = \text{lcm}(2, 4, 3) = 12 \ne 60$. Invalid.

Proof of Correctness

Theorem. $\text{ord}_m(2) = k$ if and only if $2^k \equiv 1 \pmod{m}$ and $2^{k/p} \not\equiv 1 \pmod{m}$ for every prime $p \mid k$.

Proof. The order is the smallest positive integer $d$ with $2^d \equiv 1$. If $d \mid k$ and $d \ne k$, then $d \mid k/p$ for some prime $p \mid k$ (since the quotient $k/d > 1$ has a prime factor that also divides $k$). So $2^{k/p} \equiv 1$ for that $p$. Contrapositive: if no such $p$ works, then $d = k$. $\square$

Proposition. For composite $m = m_1 m_2$ with $\gcd(m_1, m_2) = 1$, $\text{ord}_m(2) = \text{lcm}(\text{ord}_{m_1}(2), \text{ord}_{m_2}(2))$.

Proof. By CRT, $2^k \equiv 1 \pmod{m}$ iff $2^k \equiv 1 \pmod{m_i}$ for both $i$, iff $\text{ord}_{m_i}(2) \mid k$ for both $i$, iff $\text{lcm}(\text{ord}_{m_1}(2), \text{ord}_{m_2}(2)) \mid k$. $\square$

Corollary. Every valid $m$ is a divisor of $2^{60}-1$, so our enumeration is exhaustive.

Proof. $\text{ord}_m(2) = 60$ implies $m \mid 2^{60} - 1$. $\square$

Complexity Analysis

• Divisor enumeration: $O(2304)$ divisors of $2^{60} - 1$.
• Order check: $O(\log(2^{60})) = O(60)$ per divisor for modular exponentiation.
• Total: $O(2304 \cdot 60) \approx 10^5$ operations.

Answer

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

/*
 * Problem 622: Riffle Shuffles
 *
 * A perfect out-shuffle on 2n cards has order ord_{2n+1}(2).
 * Find sum of deck sizes 2n where ord_{2n+1}(2) = 60.
 *
 * Strategy: enumerate all divisors of 2^60 - 1, check which have
 * multiplicative order of 2 equal to exactly 60.
 *
 * 2^60 - 1 = 3^2 * 5^2 * 7 * 11 * 13 * 31 * 41 * 61 * 151 * 331 * 1321
 *
 * Two methods:
 *   1. Divisor enumeration with order check (primary)
 *   2. Direct order computation for small m (verification)
 */

// --- Fast modular exponentiation ---
ll power(ll base, ll exp, ll mod) {
    ll result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = (lll)result * base % mod;
        base = (lll)base * base % mod;
        exp >>= 1;
    }
    return result;
}

// --- Check if ord_m(2) == 60 ---
// Criterion: 2^60 = 1 mod m AND 2^{60/p} != 1 mod m for p in {2,3,5}
bool has_order_60(ll m) {
    if (power(2, 60, m) != 1) return false;
    if (power(2, 30, m) == 1) return false;  // 60/2
    if (power(2, 20, m) == 1) return false;  // 60/3
    if (power(2, 12, m) == 1) return false;  // 60/5
    return true;
}

// --- Direct multiplicative order (for verification) ---
ll mult_order(ll a, ll m) {
    if (m == 1) return 1;
    ll ord = 1, cur = a % m;
    while (cur != 1) {
        cur = (lll)cur * a % m;
        ord++;
        if (ord > m) return -1;
    }
    return ord;
}

// --- Method 1: Enumerate divisors of 2^60 - 1 ---
ll solve_divisor_enum() {
    vector<pair<ll, int>> factors = {
        {3, 2}, {5, 2}, {7, 1}, {11, 1}, {13, 1},
        {31, 1}, {41, 1}, {61, 1}, {151, 1}, {331, 1}, {1321, 1}
    };
    int nf = factors.size();
    vector<int> maxexp(nf);
    for (int i = 0; i < nf; i++) maxexp[i] = factors[i].second;

    ll total = 0;
    int count = 0;

    // Iterate over all exponent combinations
    vector<int> e(nf, 0);
    while (true) {
        ll d = 1;
        for (int i = 0; i < nf; i++) {
            ll pk = 1;
            for (int j = 0; j < e[i]; j++) pk *= factors[i].first;
            d *= pk;
        }

        if (d > 1 && has_order_60(d)) {
            total += d - 1;
            count++;
        }

        // Increment exponent vector (odometer)
        int carry = 1;
        for (int i = 0; i < nf && carry; i++) {
            e[i] += carry;
            if (e[i] > maxexp[i]) {
                e[i] = 0;
                carry = 1;
            } else {
                carry = 0;
            }
        }
        if (carry) break;
    }

    return total;
}

// --- Method 2: Brute force for small decks ---
ll solve_brute(int max_deck) {
    ll total = 0;
    for (int ds = 2; ds <= max_deck; ds += 2) {
        if (mult_order(2, ds + 1) == 60) {
            total += ds;
        }
    }
    return total;
}

int main() {
    // Method 1: Full solution
    ll ans1 = solve_divisor_enum();
    cout << "Divisor enumeration: " << ans1 << endl;

    // Method 2: Verify with small decks
    ll brute_small = solve_brute(10000);
    cout << "Brute force (decks <= 10000): " << brute_small << endl;

    // Cross-check: the brute force sum should match the enum sum
    // restricted to m <= 10001
    // (The full answer includes much larger m values)

    assert(ans1 == 3010983666182123972LL);
    cout << "\nAnswer: " << ans1 << endl;

    return 0;
}

"""
Problem 622: Riffle Shuffles

A perfect (out-)riffle shuffle on 2n cards has order ord_{2n+1}(2).
Find sum of deck sizes 2n where the shuffle order is exactly 60.

Key identity: ord_m(2) = 60 iff m | 2^60 - 1 and 2^{60/p} != 1 mod m
for each prime p | 60 (i.e., p in {2, 3, 5}).

2^60 - 1 = 3^2 * 5^2 * 7 * 11 * 13 * 31 * 41 * 61 * 151 * 331 * 1321

Method 1: Enumerate all divisors, check order (primary)
Method 2: Compute ord_m(2) directly for small m (verification)
"""

from itertools import product

# --- Multiplicative order ---
def mult_order(a: int, m: int):
    """Compute multiplicative order of a modulo m."""
    if m == 1:
        return 1
    order, cur = 1, a % m
    while cur != 1:
        cur = cur * a % m
        order += 1
        if order > m:
            return -1  # a and m not coprime
    return order

def check_order_exact(a: int, k: int, m: int, prime_divs: list) -> bool:
    """Check if ord_m(a) == k using the prime-divisor criterion.

    ord_m(a) = k iff a^k = 1 mod m AND a^{k/p} != 1 mod m for all primes p | k.
    """
    if pow(a, k, m) != 1:
        return False
    for p in prime_divs:
        if pow(a, k // p, m) == 1:
            return False
    return True

# --- Method 1: Enumerate divisors of 2^60 - 1 ---
def solve_divisor_enumeration():
    """Enumerate all divisors of 2^60 - 1 and find those with ord = 60."""
    # Prime factorization of 2^60 - 1
    factors = [(3, 2), (5, 2), (7, 1), (11, 1), (13, 1),
               (31, 1), (41, 1), (61, 1), (151, 1), (331, 1), (1321, 1)]

    # Verify factorization
    check = 1
    for p, e in factors:
        check *= p ** e
    assert check == 2**60 - 1, f"Factorization error: {check} != {2**60 - 1}"

    total = 0
    valid_m = []
    for exps in product(*[range(e + 1) for _, e in factors]):
        d = 1
        for i, (p, _) in enumerate(factors):
            d *= p ** exps[i]
        if d <= 1:
            continue
        if check_order_exact(2, 60, d, [2, 3, 5]):
            total += d - 1
            valid_m.append(d)

    return total, sorted(valid_m)

# --- Method 2: Brute force for small deck sizes ---
def solve_brute(target_order: int, max_deck: int = 10000):
    """Find deck sizes 2n <= max_deck with shuffle order = target_order."""
    results = []
    for deck_size in range(2, max_deck + 1, 2):
        m = deck_size + 1
        if mult_order(2, m) == target_order:
            results.append(deck_size)
    return results

# Compute and verify
answer, valid_m_list = solve_divisor_enumeration()

# Cross-check: brute force for small values
brute_results = solve_brute(60, 10000)
enum_small = [m - 1 for m in valid_m_list if m - 1 <= 10000]
assert sorted(brute_results) == sorted(enum_small), \
    f"Mismatch:\nBrute: {brute_results}\nEnum:  {enum_small}"

# Verify specific known values
assert mult_order(2, 3) == 2   # deck 2
assert mult_order(2, 5) == 4   # deck 4
assert mult_order(2, 7) == 3   # deck 6
assert mult_order(2, 9) == 6   # deck 8
assert mult_order(2, 15) == 4  # deck 14: lcm(ord_3, ord_5) = lcm(2,4) = 4

# Verify 2^60 - 1 factorization
assert 2**60 - 1 == 3**2 * 5**2 * 7 * 11 * 13 * 31 * 41 * 61 * 151 * 331 * 1321

print(f"Number of valid m values: {len(valid_m_list)}")
print(f"Smallest valid deck sizes: {[m-1 for m in valid_m_list[:10]]}")
print(f"Answer: {answer}")
assert answer == 3010983666182123972