Problem 293: Pseudo-Fortunate Numbers

Mathematical Foundation

Theorem 1 (Structure of Admissible Numbers). The set of admissible numbers $\leq N$ is finite and can be generated recursively. The consecutive primes used are $\{2, 3, 5, 7, 11, 13, 17, 19, 23\}$ since the primorial $2 \cdot 3 \cdot 5 \cdots 29 = 6{,}469{,}693{,}230 > 10^9$, while $2 \cdot 3 \cdot 5 \cdots 23 = 223{,}092{,}870 \leq 10^9$.

Proof. An admissible number must include all consecutive primes from 2 up to some prime $p_k$ with exponents $\geq 1$. The minimum admissible number using primes $\{2, 3, \ldots, p_k\}$ is the primorial $p_k\# = \prod_{i=1}^{k} p_i$. Since $29\# = 6{,}469{,}693{,}230 > 10^9$ and $23\# = 223{,}092{,}870 \leq 10^9$, admissible numbers $\leq 10^9$ use consecutive primes up to at most 23. The total count of admissible numbers is $\prod_{i=1}^{k} \lfloor \log_{p_i}(N / (N_0 / p_i^{a_i})) \rfloor$, which is bounded and equals a few thousand in practice. $\square$

Lemma 1 (Bertrand’s Postulate Bound). For any admissible number $n$, the pseudo-Fortunate number $\psi(n)$ satisfies $\psi(n) \leq n + 1$, and in practice $\psi(n) = O(\ln n)$ by the prime number theorem.

Proof. By Bertrand’s postulate, there exists a prime in $(n, 2n]$, so $\psi(n) \leq n$. More precisely, by the prime number theorem, the expected gap after $n$ is $O(\ln n)$, so $m$ is typically small (on the order of $\ln(10^9) \approx 21$). $\square$

Lemma 2 (Pseudo-Fortunate Numbers are Likely Prime). For all admissible $n$, $\psi(n)$ is itself prime.

Proof. Suppose $\psi(n) = m$ is composite, say $m = ab$ with $1 < a \leq b$. Then $n + a < n + m$ and we need to check if $n + a$ could be prime. Since $n$ is divisible by all small primes up to $p_k$, and $a < m$, if $a$ is divisible by any prime $\leq p_k$, then $n + a$ is also divisible by that prime (since $p_i \mid n$ and $p_i \mid a$ implies $p_i \mid (n + a)$), so $n + a$ is composite. However, if $a$ has no prime factor $\leq p_k$, this argument fails. Nevertheless, empirically for this problem, all pseudo-Fortunate numbers are indeed prime. This is a conjecture (related to Fortune’s conjecture) rather than a proven theorem. $\square$

Editorial

An admissible number uses consecutive primes starting from 2, each at least once. The pseudo-Fortunate number for n is the smallest m > 1 such that n + m is prime. We recursive generation of admissible numbers. We then compute pseudo-Fortunate numbers. Finally, iterate over n in admissible.

Pseudocode

Recursive generation of admissible numbers
Compute pseudo-Fortunate numbers
for n in admissible

Complexity Analysis

• Time: $O(A \cdot G \cdot \sqrt{N})$ where $A$ is the number of admissible numbers (a few thousand), $G = O(\log N)$ is the average gap to the next prime, and $\sqrt{N}$ is the cost of trial-division primality testing. With Miller—Rabin, the per-test cost drops to $O(\log^2 N)$.
• Space: $O(A)$ for storing admissible numbers and $O(|\{\psi(n)\}|)$ for the set of distinct pseudo-Fortunate numbers.

Answer

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

typedef long long ll;

const ll LIMIT = 1000000000LL;

// Small primes for generating admissible numbers
int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
int nprimes = 10;

vector<ll> admissible;

// Generate all admissible numbers <= LIMIT
// An admissible number uses consecutive primes starting from 2, each at least once
void gen_admissible(int idx, ll val) {
    admissible.push_back(val);
    if (idx >= nprimes) return;
    ll p = primes[idx];
    ll v = val * p;
    while (v <= LIMIT) {
        gen_admissible(idx + 1, v);
        if (v > LIMIT / p) break;
        v *= p;
    }
}

// Miller-Rabin primality test
typedef unsigned long long ull;
typedef __int128 lll;

ull mulmod(ull a, ull b, ull m) {
    return (lll)a * b % m;
}

ull powmod(ull a, ull b, ull m) {
    ull res = 1; a %= m;
    while (b > 0) {
        if (b & 1) res = mulmod(res, a, m);
        a = mulmod(a, a, m);
        b >>= 1;
    }
    return res;
}

bool is_prime(ull n) {
    if (n < 2) return false;
    if (n < 4) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;

    ull d = n - 1;
    int r = 0;
    while (d % 2 == 0) { d /= 2; r++; }

    for (ull a : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
        if (a >= n) continue;
        ull x = powmod(a, d, n);
        if (x == 1 || x == n - 1) continue;
        bool found = false;
        for (int i = 0; i < r - 1; i++) {
            x = mulmod(x, x, n);
            if (x == n - 1) { found = true; break; }
        }
        if (!found) return false;
    }
    return true;
}

int main() {
    // Generate admissible numbers
    // Start with prime index 0 (must include 2)
    gen_admissible(1, 2); // val=2, next prime index=1 (prime 3)
    // But also need to allow increasing exponents of prime 2
    // Actually gen_admissible starts: idx=0 means we multiply by primes[0]=2.
    // Let me fix: start with val=1, idx=0.
    admissible.clear();
    // gen_admissible(idx, val): val already includes primes[0..idx-1].
    // Now try adding primes[idx]^k for k >= 1.
    // Start: val=1, idx=0. Must add at least 2^1.

    // Re-implement:
    function<void(int, ll)> gen = [&](int idx, ll val) {
        if (idx > 0) admissible.push_back(val); // val uses primes[0..idx-1]
        if (idx >= nprimes) return;
        ll p = primes[idx];
        ll v = val * p;
        while (v <= LIMIT) {
            gen(idx + 1, v);
            if (v > LIMIT / p) break;
            v *= p;
        }
    };

    gen(0, 1);

    // Find pseudo-Fortunate numbers
    set<ll> pf_set;
    for (ll n : admissible) {
        for (ll m = 2; ; m++) {
            if (is_prime(n + m)) {
                pf_set.insert(m);
                break;
            }
        }
    }

    ll sum = 0;
    for (ll m : pf_set) sum += m;
    cout << sum << endl;

    return 0;
}

"""
Problem 293: Pseudo-Fortunate Numbers

Find the sum of all distinct pseudo-Fortunate numbers for admissible numbers <= 10^9.

An admissible number uses consecutive primes starting from 2, each at least once.
The pseudo-Fortunate number for n is the smallest m > 1 such that n + m is prime.
"""

from sympy import isprime

LIMIT = 10**9
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

def gen_admissible():
    """Generate all admissible numbers <= LIMIT."""
    result = []

    def gen(idx, val):
        if idx > 0:
            result.append(val)
        if idx >= len(primes):
            return
        p = primes[idx]
        v = val * p
        while v <= LIMIT:
            gen(idx + 1, v)
            v *= p

    gen(0, 1)
    return result

def solve():
    admissible = gen_admissible()
    pf_set = set()

    for n in admissible:
        m = 2
        while not isprime(n + m):
            m += 1
        pf_set.add(m)

    print(sum(pf_set))

if __name__ == "__main__":
    solve()