Problem 263: An Engineers’ Dream Come True

Mathematical Foundation

Definition. A positive integer $m$ is practical if every integer $1 \le k \le m$ can be represented as a sum of distinct divisors of $m$.

Theorem 1 (Stewart’s criterion). A positive integer $m \ge 2$ is practical if and only if $m$ is even and, writing $m = p_1^{a_1} p_2^{a_2} \cdots p_r^{a_r}$ with $p_1 < p_2 < \cdots < p_r$, we have for each $i \ge 2$:

where $\sigma$ denotes the sum-of-divisors function.

Proof. See B. M. Stewart, “Sums of distinct divisors,” Amer. J. Math. 76 (1954), 779—785. The forward direction: if $p_i > 1 + \sigma(p_1^{a_1}\cdots p_{i-1}^{a_{i-1}})$, then the integer $1 + \sigma(p_1^{a_1}\cdots p_{i-1}^{a_{i-1}})$ cannot be represented. The reverse: if the condition holds for all $i$, an inductive construction shows every integer up to $\sigma(m)$ (hence up to $m$) is representable. $\square$

Lemma 1 (Modular constraints on $n$). If $n-9, n-3, n+3, n+9$ are all primes greater than 5, then $n \equiv 10$ or $20 \pmod{30}$.

Proof.

• Modulo 2: The four values $n \pm 3$, $n \pm 9$ must be odd, so $n$ is even.
• Modulo 3: Since $n - 9 \equiv n \pmod{3}$ and $n - 3 \equiv n \pmod{3}$, all four values are $\equiv n \pmod{3}$. For none to be divisible by 3, we need $n \not\equiv 0 \pmod{3}$.
• Modulo 5: The residues $n - 9, n - 3, n + 3, n + 9$ modulo 5 are $n+1, n+2, n+3, n+4$. For none to be $0 \pmod{5}$, we need $n \equiv 0 \pmod{5}$.

Combining: $n \equiv 0 \pmod{2}$, $n \not\equiv 0 \pmod{3}$, $n \equiv 0 \pmod{5}$. By the Chinese Remainder Theorem, $n \equiv 10$ or $20 \pmod{30}$. $\square$

Lemma 2 (Consecutivity conditions). For the four primes to be consecutive, the six intermediate odd values $n - 7, n - 5, n - 1, n + 1, n + 5, n + 7$ must all be composite.

Proof. Since $n$ is even, the only integers strictly between consecutive members of $\{n-9, n-3, n+3, n+9\}$ that could be prime are the odd ones: $n-7, n-5$ (between $n-9$ and $n-3$), $n-1, n+1$ (between $n-3$ and $n+3$), and $n+5, n+7$ (between $n+3$ and $n+9$). All must be composite for consecutivity. $\square$

Editorial

Definitions: i.e., (p, p+6), (p+6, p+12), (p+12, p+18) with all four consecutive primes. (1) n-9, n-3, n+3, n+9 are all prime AND are four consecutive primes (no primes between them: n-7, n-5, n-1, n+1, n+5, n+7 all composite) (2) n-8, n-4, n, n+4, n+8 are all practical numbers Key observations:. We sieve primes up to 1.2 * 10^9 using Sieve of Eratosthenes.

Pseudocode

Sieve primes up to 1.2 * 10^9 using Sieve of Eratosthenes
results = []
return sum(results)

Complexity Analysis

• Time: $O(N \log \log N)$ for the Sieve of Eratosthenes up to $N \approx 1.2 \times 10^9$. The main loop iterates over $O(N/15)$ candidates. Each practical-number test factors $m$ in $O(\sqrt{m})$ and checks Stewart’s criterion in $O(\log m)$. Total: $O(N \log \log N)$.
• Space: $O(N)$ for the prime sieve bitmap.

Answer

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

/*
 * Problem 263: An Engineers' Dream Come True
 *
 * Find first 4 "engineers' paradises" n such that:
 * - n-9, n-3, n+3, n+9 are all prime (sexy prime quadruplet)
 * - (n-9, n-3), (n-3, n+3), (n+3, n+9) are CONSECUTIVE prime pairs
 *   (no primes between them: n-7, n-5, n-1, n+1, n+5, n+7 all composite)
 * - n-8, n-4, n, n+4, n+8 are all practical numbers
 *
 * n ≡ 10 or 20 (mod 30).
 *
 * Answer: 2039506520
 */

const int LIMIT = 1200000010;
vector<bool> is_prime_sieve;

void build_sieve() {
    is_prime_sieve.assign(LIMIT + 1, true);
    is_prime_sieve[0] = is_prime_sieve[1] = false;
    for (ll i = 2; i * i <= LIMIT; i++) {
        if (is_prime_sieve[i]) {
            for (ll j = i * i; j <= LIMIT; j += i)
                is_prime_sieve[j] = false;
        }
    }
}

bool is_practical(ll n) {
    if (n <= 0) return false;
    if (n == 1) return true;
    if (n % 2 != 0) return false;
    vector<pair<ll,int>> factors;
    ll temp = n;
    for (ll d = 2; d * d <= temp; d++) {
        if (temp % d == 0) {
            int e = 0;
            while (temp % d == 0) { temp /= d; e++; }
            factors.push_back({d, e});
        }
    }
    if (temp > 1) factors.push_back({temp, 1});
    sort(factors.begin(), factors.end());
    if (factors[0].first != 2) return false;
    ll sigma = 1;
    for (int i = 0; i < (int)factors.size(); i++) {
        ll p = factors[i].first;
        int a = factors[i].second;
        if (i == 0) {
            ll pw = 1;
            for (int j = 0; j <= a; j++) pw *= p;
            sigma = (pw - 1) / (p - 1);
        } else {
            if (p > 1 + sigma) return false;
            ll pw = 1;
            for (int j = 0; j <= a; j++) pw *= p;
            sigma *= (pw - 1) / (p - 1);
        }
    }
    return true;
}

int main() {
    fprintf(stderr, "Building sieve up to %d...\n", LIMIT);
    build_sieve();
    fprintf(stderr, "Sieve done.\n");

    vector<ll> results;
    for (ll n = 10; n <= 1200000000LL && (int)results.size() < 4; n += 10) {
        int r = n % 30;
        if (r != 10 && r != 20) continue;

        // Check four primes
        if (!is_prime_sieve[n-9] || !is_prime_sieve[n+9] ||
            !is_prime_sieve[n-3] || !is_prime_sieve[n+3])
            continue;

        // Check consecutive: no primes between the pairs
        // n-7, n-5 must be composite (between n-9 and n-3)
        // n-1, n+1 must be composite (between n-3 and n+3)
        // n+5, n+7 must be composite (between n+3 and n+9)
        if (is_prime_sieve[n-7] || is_prime_sieve[n-5] ||
            is_prime_sieve[n-1] || is_prime_sieve[n+1] ||
            is_prime_sieve[n+5] || is_prime_sieve[n+7])
            continue;

        // Check five practical numbers
        if (is_practical(n-8) && is_practical(n-4) &&
            is_practical(n) && is_practical(n+4) &&
            is_practical(n+8)) {
            results.push_back(n);
            fprintf(stderr, "Found n = %lld (%lu/4)\n", n, results.size());
        }
    }

    ll ans = 0;
    for (ll x : results) ans += x;
    cout << ans << endl;
    return 0;
}

"""
Problem 263: An Engineers' Dream Come True

Definitions:
- Practical number: every integer 1..n is a sum of distinct divisors of n.
- Sexy pair: a pair of CONSECUTIVE primes differing by 6. First: (23, 29).
- Triple-pair: three consecutive sexy pairs where second member = first of next.
  i.e., (p, p+6), (p+6, p+12), (p+12, p+18) with all four consecutive primes.
- Engineers' paradise: n such that:
  (1) n-9, n-3, n+3, n+9 are all prime AND are four consecutive primes
      (no primes between them: n-7, n-5, n-1, n+1, n+5, n+7 all composite)
  (2) n-8, n-4, n, n+4, n+8 are all practical numbers

Key observations:
- n must be congruent to 10 or 20 (mod 30).
- The four values are: 219869980, 312501820, 360613700, 1146521020.

Answer: 2039506520
"""

import math

def sieve_primes(limit):
    """Simple sieve of Eratosthenes returning a boolean array."""
    is_prime = bytearray([1]) * (limit + 1)
    is_prime[0] = is_prime[1] = 0
    for i in range(2, int(math.isqrt(limit)) + 1):
        if is_prime[i]:
            for j in range(i*i, limit + 1, i):
                is_prime[j] = 0
    return is_prime

def is_practical(n):
    """Check if n is a practical number using Stewart's criterion."""
    if n <= 0: return False
    if n == 1: return True
    if n % 2 != 0: return False
    factors = []
    temp = n
    d = 2
    while d * d <= temp:
        if temp % d == 0:
            exp = 0
            while temp % d == 0:
                temp //= d
                exp += 1
            factors.append((d, exp))
        d += 1
    if temp > 1:
        factors.append((temp, 1))
    factors.sort()
    if factors[0][0] != 2: return False
    sigma_product = 1
    for i, (p, a) in enumerate(factors):
        if i == 0:
            sigma_product = (p ** (a + 1) - 1) // (p - 1)
        else:
            if p > 1 + sigma_product: return False
            sigma_product *= (p ** (a + 1) - 1) // (p - 1)
    return True

def solve():
    LIMIT = 1_200_000_000

    print("Sieving primes...", flush=True)
    is_prime = sieve_primes(LIMIT + 10)
    print("Sieve done.", flush=True)

    results = []
    n = 10
    while n <= LIMIT and len(results) < 4:
        r = n % 30
        if r == 10 or r == 20:
            # Check four primes
            if (is_prime[n - 9] and is_prime[n - 3] and
                is_prime[n + 3] and is_prime[n + 9]):
                # Check consecutive: no primes between the pairs
                if not (is_prime[n-7] or is_prime[n-5] or
                        is_prime[n-1] or is_prime[n+1] or
                        is_prime[n+5] or is_prime[n+7]):
                    # Check five practical numbers
                    if (is_practical(n - 8) and is_practical(n - 4) and
                        is_practical(n) and is_practical(n + 4) and
                        is_practical(n + 8)):
                        results.append(n)
                        print(f"Found n = {n} ({len(results)}/4)", flush=True)
        n += 10

    print(sum(results))

if __name__ == "__main__":
    solve()