Problem 293: Pseudo-Fortunate Numbers

Project Euler Problem 293 Solution

EulerSolve provides an optimized solution for Project Euler Problem 293, Pseudo-Fortunate Numbers, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary An even integer $n$ is called admissible when it is either a power of $2$ or, equivalently for even numbers, its distinct prime factors form a consecutive prefix of the prime list $2,3,5,7,\ldots$. For every admissible $n < 10^9$, define $M(n)$ as the smallest integer $m>1$ such that $n+m$ is prime. The task is to sum the distinct values of $M(n)$. Mathematical Approach 1. Exact shape of admissible numbers Because $n$ is even, the first prime $2$ must appear. If the distinct prime factors are consecutive, then every admissible number has the form $$n = 2^{a_1} 3^{a_2} 5^{a_3} \cdots p_k^{a_k}, \qquad a_i \ge 1.$$ The special case "power of $2$" is simply the case $k=1$. So admissible numbers are described completely by choosing a prime prefix and choosing a positive exponent for each prime in that prefix. This already gives a strong bound on the search space. The product of the first nine primes is $$2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\cdot 19\cdot 23 = 223092870 < 10^9,$$ while including the next prime gives $$223092870 \cdot 29 = 6469693230 > 10^9.$$ Therefore no admissible number below $10^9$ can contain $29$ or any later prime as a distinct factor. The code keeps a slightly longer fixed prime list, but recursion automatically prunes everything beyond the limit. 2....

Detailed mathematical approach

Problem Summary

An even positive integer $N$ is called admissible if it is a power of $2$ or its distinct prime factors are consecutive primes; the first twelve are $2$, $4$, $6$, $8$, $12$, $16$, $18$, $24$, $30$, $32$, $36$ and $48$. For an admissible $N$, the pseudo-Fortunate number is the smallest integer $M\gt1$ such that $N+M$ is prime. For example, $630=2\cdot3^2\cdot5\cdot7$ is admissible and the next prime after $631$ is $641$, so its pseudo-Fortunate number is $M=11$; that of $16$ is $3$. We must find the sum of all distinct pseudo-Fortunate numbers of the admissible $N\lt10^9$, each value counted once. ^[1] The name comes from the Fortunate numbers of Reo Fortune, the same offsets for the products $2$, $2\cdot3$, $2\cdot3\cdot5$, … of the first primes. ^[2]

The whole solution in one sentence: the admissible numbers are the products of the first few primes, each used at least once, so the $6656$ of them below $10^9$ can be generated one by one, and for each one we test $N+3$, $N+5$, … for primality until a prime appears and add up the different offsets found.

Mathematical Approach

We describe and list the admissible numbers, then study which offsets can work, why $M$ need not be prime, and how primality is tested exactly.

1. Small cases

Below $50$, the even numbers that are not admissible skip a prime, for example $10=2\cdot5$ and $20=2^2\cdot5$ miss $3$, $14=2\cdot7$ misses $3$ and $5$, and $42=2\cdot3\cdot7$ misses $5$. For the twelve admissible ones, searching upwards from $N+2$ for the first prime gives:

$M=3$ for $N=2,4,8,16$, with the primes $5,7,11,19$;
$M=5$ for $N=6,12,18,24,32,36,48$, with the primes $11,17,23,29,37,41,53$;
$M=7$ for $N=30$, with the prime $37$.

Every $M$ is odd, the value $3$ occurs only for powers of $2$, and $30=2\cdot3\cdot5$ needs $M=7$. Sections 5 and 6 explain why.

2. What admissible numbers look like

Write $p_1=2$, $p_2=3$, $p_3=5$, … for the primes in increasing order.

Claim. $N$ is admissible exactly when

$$N=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$$

for some $k\ge1$ and exponents $a_1,\dots,a_k\ge1$.

Proof. An admissible $N$ is even, so $2$ is one of its prime factors. A power of $2$ has this form with $k=1$. Otherwise the distinct prime factors form a run of consecutive primes that contains the smallest prime $2$, so the run starts there and consists of $p_1,\dots,p_k$. Conversely, such a product is even, and its distinct prime factors $p_1,\dots,p_k$ are consecutive primes, or just $2$ when $k=1$. By the fundamental theorem of arithmetic an integer greater than $1$ is a product of primes in only one way, ^[6] so different exponent lists give different numbers.

These are the terms of OEIS A055932 except its odd first term $1$. ^[4] From now on $k$ is the number of distinct prime factors of $N$, so $p_{k+1}$ is the smallest prime that does not divide $N$; for $N=630$, $k=4$ and $p_5=11$.

3. At most nine primes

With $k$ primes, the smallest admissible number takes every exponent equal to $1$; it is the primorial $p_k\#=p_1p_2\cdots p_k$. The primorials are $2$, $6$, $30$, $210$, $2310$, $30030$, $510510$, $9699690$, $223092870$ and then $6469693230$. ^[5] Since

$$\begin{aligned}p_9\#&=223092870\lt10^9,\\ p_{10}\#&=6469693230\gt10^9,\end{aligned}$$

every admissible $N\lt10^9$ has $k\le9$ and is built from the primes $2,3,5,\dots,23$ only.

4. Listing them by depth-first search

Section 2 turns the listing into a sequence of choices: an exponent $a_1\ge1$ for $2$, then either stop or choose $a_2\ge1$ for $3$, and so on. The choices form a tree in which the children of a node $c$ built from $i$ primes are $c\,p_{i+1}$, $c\,p_{i+1}^2$, …. A depth-first search walks through it one branch at a time. Multiplying never makes a number smaller, so once a product reaches the limit $L$, the search stops raising that power and skips everything below that product.

For $L=100$ the branch of $2$ gives $2,6,30,18,90,54$ in this order: after $6=2\cdot3$ and $30=6\cdot5$, both $30\cdot5$ and $30\cdot7$ are too large, so the search goes on with $18=2\cdot3^2$, its child $90$, and $54=2\cdot3^3$. The branches of $4$, $8$, $16$, $32$ and $64$ give $4,12,60,36$, then $8,24,72$, $16,48$, $32,96$ and $64$: the $18$ admissible numbers below $100$.

Claim. The search produces every admissible number below $L$ exactly once, and nothing else.

Proof. Everything produced has the form of Section 2 and is below $L$. An admissible $N=p_1^{a_1}\cdots p_k^{a_k}\lt L$ is reached by choosing $a_1,\dots,a_k$ in turn; every number on this path divides $N$, so it is below $L$, and the path is never cut. Different paths give different exponent lists, hence different numbers.

For $L=10^9$ there are $6656$ admissible numbers: $29$, $258$, $933$, $1831$, $1900$, $1212$, $416$, $73$ and $4$ of them for $k=1,\dots,9$. For $k=1$ they are the powers $2^1,\dots,2^{29}$, and for $k=9$ they are $p_9\#$ times $1$, $2$, $3$, $4$.

5. Only odd offsets

If $M\gt1$, then $N+M\ge N+2\ge4$, so a prime $N+M$ is odd. As $N$ is even, $M$ must be odd, and the candidates are $m=3,5,7,\dots$.

6. Offsets that share a prime with $N$ fail

Claim. If a prime $q$ divides both $N$ and an offset $m\ge2$, then $N+m$ is not prime. Hence no prime below $p_{k+1}$ divides $M$, and $M\ge p_{k+1}$.

Proof. The prime $q$ divides $N+m$, and $N+m\gt m\ge q$, so $N+m$ is composite. The primes below $p_{k+1}$ are $p_1,\dots,p_k$, and all of them divide $N$. Every $m$ with $1\lt m\lt p_{k+1}$ has a prime factor of at most $m$, which is one of them, so it fails.

For $N=630$ every odd offset below $p_5=11$ fails in this way: $633=3\cdot211$, $635=5\cdot127$, $637=7^2\cdot13$ and $639=3^2\cdot71$. Then $641$ is prime, so $M=11$. For $N=16$, $p_2=3$ and $19$ is prime, so $M=3$. Multiples of $6$ therefore have $M\ge5$, and multiples of $30$ have $M\ge7$, as in Section 1. The same argument is known for the Fortunate numbers. ^[2]

7. $M$ is usually prime, but not always

Claim. If $M\lt p_{k+1}^2$, then $M$ is prime.

Proof. A composite $M$ has at least two prime factors, counted with multiplicity, and by Section 6 each of them is at least $p_{k+1}$, so $M\ge p_{k+1}^2$.

For the primorials, the admissible numbers with all exponents $1$, the pseudo-Fortunate numbers are the Fortunate numbers $3,5,7,13,23,17,19,23,37$ for $k=1,\dots,9$. ^[3] Each is below $p_{k+1}^2$, for $k=9$ for example $37\lt29^2$, so the claim proves them prime. Fortune conjectured that every Fortunate number is prime; this is open, but the several thousand computed so far are all prime. ^[2] ^[3]

With few primes, however, $p_{k+1}^2$ is small, and composite values occur. For $N=512=2^9$ the offsets $3$, $5$ and $7$ give $515=5\cdot103$, $517=11\cdot47$ and $519=3\cdot173$, while $521$ is prime, so $M=9$. For $k=2$ the smallest possible composite value is $25$, and $N=147456=2^{14}\cdot3^2$ has $M=25$. Below $10^9$, $43$ admissible numbers have a composite $M$, all of them with $k\le3$. Composite offsets must therefore be allowed: a search over prime offsets only would give $11$ for $N=512$, since $523$ is prime, and below $1000$ it would find the sum $39$ instead of $48$.

8. Distinct values

The sum takes each value once. Below $100$ the $18$ admissible numbers give only $3$, $5$ and $7$, with the sum $15$. Below $1000$ the $56$ admissible numbers give $3,5,7,9,11,13$, with the sum $48$, and $9$ comes from $N=512$ alone. Below $10^4$ the $147$ admissible numbers give $3,5,7,9,11,13,17,19,23$, with the sum $107$.

9. An exact primality test

Each step of a search asks whether a number $n=N+m\lt2^{30}$ is prime. Trial division would need up to $3401$ divisions for a prime near $10^9$, one for each prime up to $\sqrt n\approx31622$; the Miller–Rabin test needs a few multiplications per binary digit of $n$ for each base. It works with remainders: $u\equiv v\pmod n$ means that $u$ and $v$ leave the same remainder after division by $n$. For example $32^2=1024=641+383$, so $32^2\equiv383\pmod{641}$; powers are computed by repeated squaring, keeping only the remainders. Write $n-1=2^sd$ with $d$ odd, where $s\ge1$ because $n$ is odd. Then $n$ is a strong probable prime to the base $a$ if $a^d\equiv1\pmod n$, or if $a^{2^rd}\equiv-1\pmod n$ for some $r$ with $0\le r\lt s$. ^[7]

An odd prime $n$ passes for every base that it does not divide: by Fermat's little theorem the chain of squares $a^d,a^{2d},\dots,a^{2^sd}$ ends with $1$, and its first $1$ is either $a^d$ or the square of some $x\not\equiv1$. That $x$ must be $-1$: the prime $n$ divides $x^2-1=(x-1)(x+1)$, hence one of the two factors, and not $x-1$. ^[7] For $641$, with $640=2^7\cdot5$, the base $2$ gives the chain $32$, $383$, $541$, $385$, $154$, $640\equiv-1$.

A composite number that passes is a strong pseudoprime to the base $a$. For $2047=23\cdot89$ we have $2046=2\cdot1023$ and $2^{11}=2048\equiv1$, so $2^{1023}=(2^{11})^{93}\equiv1\pmod{2047}$, and the base $2$ is fooled, although it suffices below $2047$. ^[7] Several bases together leave no exceptions in a range: $2$, $3$, $5$, $7$ for $n\lt3\,215\,031\,751$, ^[7] and the seven bases $2$, $325$, $9375$, $28178$, $450775$, $9780504$, $1795265022$, found by Jim Sinclair in 2011, for $n\lt2^{64}$. A base that is a multiple of $n$ counts as passed, and every base has to be tested, also those larger than $n$. ^[8] The programs use the seven bases.

How the Code Works

The C++ program ^[10] starts in main. parse_arguments accepts --skip-checkpoints and --limit= followed by digits, which it reads without an overflow check; the default limit is $10^9$, and an unknown argument or a limit below $3$ gives exit code $1$. Unless skipped, run_checkpoints requires pseudo_fortunate(16) == 3 and pseudo_fortunate(630) == 11 and compares solve(10000) with solve_bruteforce(10000); a failure gives exit code $2$. Then the program prints solve(limit).

solve takes the eleven primes from $2$ to $31$ from prime_prefix; only nine of them occur below $10^9$ (Section 3), and the list suffices for every limit up to $p_{12}\#=7420738134810$. generate_admissible is the search of Section 4: it multiplies value by the current prime $p$ while value <= (limit - 1) / p, so the product stays below the limit and cannot overflow, inserts each product into the std::set<u64> named admissible and recurses with the next prime. For each element, pseudo_fortunate tries $m=3,5,7,\dots$ until is_prime(n + m) holds, composite $m$ included (Sections 5 and 7). The results go into a std::set<int>, which keeps each value once, and are added in a u64. Offsets excluded by Section 6 are still tested, but cheaply: the common prime factor is at most $23$, so $N+m$ fails in the trial divisions.

is_prime implements Section 9. It settles $n\lt2$ and the multiples of the twelve primes up to $37$, splits $n-1=2^sd$ and runs the seven bases, skipping a base with a % n == 0 as passed. mod_pow computes $a^d\bmod n$ by repeated squaring with every product formed as an unsigned __int128, so the test is valid for all 64-bit $n$. After the trial divisions only the composite $14089=73\cdot193$ divides a base, and the base $2$ rejects it. solve_bruteforce scans all even numbers below the limit with is_admissible_bruteforce, which factors $n$ by trial division and accepts it when its distinct primes are $2,3,5,\dots$ without a gap; this checks Sections 2 and 4, while the primality test is shared.

The Python and Java programs contain the same functions without options, checkpoints or brute force. Python uses the built-in three-argument pow and unlimited integers; Java multiplies residues with BigInteger, which is safe for every long $n$.

Complexity and Verification

With $A$ admissible numbers and $T$ calls of is_prime, the C++ program needs $O(A\log A)$ time for its two ordered sets and $O(T\log n)$ for the primality tests; the hash sets of Python and Java take $O(A)$ expected time instead. Here $A=6656$, and since a pseudo-Fortunate search makes $(M-1)/2$ calls, $T=70472$, about $10.6$ per $N$. The mean of $M$ is about $22$, and the longest search, for $N=338688000$, that is $2^{11}\cdot3^3\cdot5^3\cdot7^2$, makes $65$ calls and ends at $M=131$. Of all calls, $52860$ reject a composite in the trial divisions and $10956$ at the first base, and $6646$ primes pass all seven bases (the other $10$ primes are at most $37$); since $n\lt2^{30}$, a base costs at most about $60$ modular multiplications. Bertrand's postulate gives a prime between $N+1$ and $2N+2$, ^[9] so every search ends with $M\le N+1$, which fits in an int. The memory is $O(A)$ for the sets, plus a recursion at most ten calls deep. On an Apple M4 Max each of the three programs finishes within a quarter of a second.

The C++ checkpoints test the two values of the statement and compare the search with the brute force below $10^4$. For this article the following checks were run in addition, outside the published programs:

A test of the definition by factoring finds the same $450$ admissible numbers below $2\cdot10^5$ as the search.
An independent computation of all $6656$ values of $M$, with every prime confirmed by trial division, gives the same final value as the C++ program built with g++ and with clang++, the Python program and the Java program. It confirms the facts of Sections 6 to 8, and the C++ program reproduces the sums of Section 8 with --limit=100, --limit=1000 and --limit=10000.
The published is_prime agrees with a sieve of Eratosthenes for all $n\le5\cdot10^7$ and with trial division on all $70472$ numbers that the searches test.

Footnotes and References

The references supply the background facts; the description and listing of the admissible numbers, the bounds of Sections 6 and 7 and all counts are derived or computed in this article.

Project Euler 293 — Pseudo-Fortunate Numbers. The official statement defines admissible numbers and their pseudo-Fortunate numbers, gives M = 11 for N = 630 and M = 3 for N = 16, and asks for the sum of all distinct pseudo-Fortunate numbers for admissible N below 10⁹.
Wikipedia — Fortunate number. The Fortunate number of p_n# is the smallest m > 1 with p_n# + m prime. Reo Fortune conjectured that none is composite; as of 2017 all known ones are prime, checked up to n = 3000. The divisors other than 1 of the Fortunate number of p_n# exceed p_n, so a composite one would be at least p_(n+1)².
OEIS A005235 — Fortunate numbers. The sequence begins 3, 5, 7, 13, 23, 17, 19, 23, 37, 61, …; its comments record Fortune's conjecture, report that the first several thousand terms are primes, and note that a term below prime(n+1)² is prime.
OEIS A055932 — Numbers all of whose prime divisors are consecutive primes starting at 2. The sequence begins 1, 2, 4, 6, 8, 12, 16, 18, 24, 30, 32, 36, 48, 54, 60, …; apart from 1 its terms are the admissible numbers.
Wikipedia — Primorial. The primorial p_n# is the product of the first n primes; the table of the article lists its values for n ≤ 12, from 2, 6, 30, 210 to 223092870, 6469693230, 200560490130 and 7420738134810.
Wikipedia — Fundamental theorem of arithmetic. Every integer greater than 1 is prime or a product of primes in exactly one way, up to the order of the factors.
Wikipedia — Miller–Rabin primality test. The article defines strong probable primes through n − 1 = 2^s·d, explains with Fermat's little theorem why every prime passes, and states that the base 2 suffices for n < 2047 and the bases 2, 3, 5, 7 for n < 3,215,031,751.
W. Izykowski — Deterministic variants of the Miller-Rabin primality test. The table of best known base sets lists the seven bases found by Jim Sinclair in 2011 as deterministic below 2^64; its remarks say that a witness may need reducing modulo n, that a witness reduced to 0 counts as passed, and that all bases must be tested.
Wikipedia — Bertrand's postulate. For every integer n > 1 there is a prime p with n < p < 2n; Chebyshev proved it in 1852.
C++ — Euler293.cpp. The linked immutable revision contains generate_admissible, pseudo_fortunate, is_prime, solve_bruteforce and run_checkpoints; it is the implementation record for this article.

Problem 293 source code

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <set>
#include <string>
#include <vector>

namespace {

using u64 = std::uint64_t;
using u128 = unsigned __int128;

struct Options {
    u64 limit = 1000000000ULL;
    bool run_checkpoints = true;
};

bool parse_u64_after_prefix(const std::string& arg, const std::string& prefix, u64& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }
    u64 parsed = 0ULL;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10ULL + static_cast<u64>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_u64_after_prefix(arg, "--limit=", options.limit)) {
            continue;
        }
        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.limit >= 3ULL;
}

u64 mod_pow(u64 base, u64 exp, u64 mod) {
    u64 result = 1ULL % mod;
    u64 cur = base % mod;
    while (exp > 0ULL) {
        if ((exp & 1ULL) != 0ULL) {
            result = static_cast<u64>((static_cast<u128>(result) * cur) % mod);
        }
        cur = static_cast<u64>((static_cast<u128>(cur) * cur) % mod);
        exp >>= 1U;
    }
    return result;
}

bool is_prime(const u64 n) {
    if (n < 2ULL) {
        return false;
    }
    for (u64 p : {2ULL, 3ULL, 5ULL, 7ULL, 11ULL, 13ULL, 17ULL, 19ULL, 23ULL, 29ULL, 31ULL, 37ULL}) {
        if (n == p) {
            return true;
        }
        if (n % p == 0ULL) {
            return false;
        }
    }

    u64 d = n - 1ULL;
    int s = 0;
    while ((d & 1ULL) == 0ULL) {
        d >>= 1U;
        ++s;
    }

    for (u64 a : {2ULL, 325ULL, 9375ULL, 28178ULL, 450775ULL, 9780504ULL, 1795265022ULL}) {
        if (a % n == 0ULL) {
            continue;
        }
        u64 x = mod_pow(a, d, n);
        if (x == 1ULL || x == n - 1ULL) {
            continue;
        }
        bool witness = true;
        for (int r = 1; r < s; ++r) {
            x = static_cast<u64>((static_cast<u128>(x) * x) % n);
            if (x == n - 1ULL) {
                witness = false;
                break;
            }
        }
        if (witness) {
            return false;
        }
    }
    return true;
}

std::vector<int> prime_prefix() {
    return {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
}

void generate_admissible(const std::vector<int>& primes,
                         const int idx,
                         const u64 current,
                         const u64 limit,
                         std::set<u64>& out) {
    if (idx >= static_cast<int>(primes.size())) {
        return;
    }
    const u64 p = static_cast<u64>(primes[static_cast<std::size_t>(idx)]);
    u64 value = current;
    while (value <= (limit - 1ULL) / p) {
        value *= p;
        out.insert(value);
        generate_admissible(primes, idx + 1, value, limit, out);
    }
}

int pseudo_fortunate(const u64 n) {
    for (int m = 3;; m += 2) {
        if (is_prime(n + static_cast<u64>(m))) {
            return m;
        }
    }
}

u64 solve(const u64 limit) {
    std::set<u64> admissible;
    const auto primes = prime_prefix();
    generate_admissible(primes, 0, 1ULL, limit, admissible);

    std::set<int> pseudo_values;
    for (u64 n : admissible) {
        pseudo_values.insert(pseudo_fortunate(n));
    }

    u64 sum = 0ULL;
    for (int m : pseudo_values) {
        sum += static_cast<u64>(m);
    }
    return sum;
}

bool is_admissible_bruteforce(u64 n) {
    if ((n & 1ULL) == 1ULL) {
        return false;
    }
    std::vector<u64> factors;
    u64 x = n;
    for (u64 p = 2ULL; p * p <= x; ++p) {
        if (x % p != 0ULL) {
            continue;
        }
        factors.push_back(p);
        while (x % p == 0ULL) {
            x /= p;
        }
    }
    if (x > 1ULL) {
        factors.push_back(x);
    }
    if (factors.empty() || factors[0] != 2ULL) {
        return false;
    }
    u64 candidate = 2ULL;
    std::size_t idx = 0;
    while (idx < factors.size()) {
        if (factors[idx] != candidate) {
            return false;
        }
        ++idx;
        ++candidate;
        while (!is_prime(candidate)) {
            ++candidate;
        }
    }
    return true;
}

u64 solve_bruteforce(const u64 limit) {
    std::set<int> pseudo_values;
    for (u64 n = 2; n < limit; n += 2) {
        if (!is_admissible_bruteforce(n)) {
            continue;
        }
        pseudo_values.insert(pseudo_fortunate(n));
    }
    u64 sum = 0ULL;
    for (int m : pseudo_values) {
        sum += static_cast<u64>(m);
    }
    return sum;
}

bool run_checkpoints() {
    if (pseudo_fortunate(16ULL) != 3) {
        std::cerr << "Checkpoint failed for N=16 sample" << '\n';
        return false;
    }
    if (pseudo_fortunate(630ULL) != 11) {
        std::cerr << "Checkpoint failed for N=630 sample" << '\n';
        return false;
    }
    if (solve(10000ULL) != solve_bruteforce(10000ULL)) {
        std::cerr << "Checkpoint failed for brute cross-check at limit=10000" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }
    std::cout << solve(options.limit) << '\n';
    return 0;
}

Python

def mod_pow(base, exp, mod):
    return pow(base, exp, mod)

def is_prime(n):
    if n < 2:
        return False
    for p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]:
        if n == p:
            return True
        if n % p == 0:
            return False

    d = n - 1
    s = 0
    while (d & 1) == 0:
        d >>= 1
        s += 1

    for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
        if a % n == 0:
            continue
        x = mod_pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        witness = True
        for _ in range(1, s):
            x = (x * x) % n
            if x == n - 1:
                witness = False
                break
        if witness:
            return False
    return True

def prime_prefix():
    return [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]

def generate_admissible(primes, idx, current, limit, out):
    if idx >= len(primes):
        return
    p = primes[idx]
    value = current
    while value <= (limit - 1) // p:
        value *= p
        out.add(value)
        generate_admissible(primes, idx + 1, value, limit, out)

def pseudo_fortunate(n):
    m = 3
    while True:
        if is_prime(n + m):
            return m
        m += 2

def solve(limit=1000000000):
    admissible = set()
    primes = prime_prefix()
    generate_admissible(primes, 0, 1, limit, admissible)

    pseudo_values = set()
    for n in admissible:
        pseudo_values.add(pseudo_fortunate(n))

    return str(sum(pseudo_values))

if __name__ == '__main__':
    print(solve())

Java

import java.util.*;

public class Euler293 {
    static long modPow(long base, long exp, long mod) {
        long result = 1L % mod;
        long cur = base % mod;
        while (exp > 0) {
            if ((exp & 1) != 0) {
                // To avoid overflow, use BigInteger for multiplication modulo
                result = java.math.BigInteger.valueOf(result)
                        .multiply(java.math.BigInteger.valueOf(cur))
                        .mod(java.math.BigInteger.valueOf(mod)).longValue();
            }
            cur = java.math.BigInteger.valueOf(cur)
                    .multiply(java.math.BigInteger.valueOf(cur))
                    .mod(java.math.BigInteger.valueOf(mod)).longValue();
            exp >>= 1;
        }
        return result;
    }

    static boolean isPrime(long n) {
        if (n < 2)
            return false;
        long[] smallPrimes = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 };
        for (long p : smallPrimes) {
            if (n == p)
                return true;
            if (n % p == 0)
                return false;
        }

        long d = n - 1;
        int s = 0;
        while ((d & 1) == 0) {
            d >>= 1;
            ++s;
        }

        long[] bases = { 2, 325, 9375, 28178, 450775, 9780504, 1795265022 };
        for (long a : bases) {
            if (a % n == 0)
                continue;
            long x = modPow(a, d, n);
            if (x == 1 || x == n - 1)
                continue;
            boolean witness = true;
            for (int r = 1; r < s; ++r) {
                x = java.math.BigInteger.valueOf(x)
                        .multiply(java.math.BigInteger.valueOf(x))
                        .mod(java.math.BigInteger.valueOf(n)).longValue();
                if (x == n - 1) {
                    witness = false;
                    break;
                }
            }
            if (witness)
                return false;
        }
        return true;
    }

    static void generateAdmissible(int[] primes, int idx, long current, long limit, Set<Long> out) {
        if (idx >= primes.length)
            return;
        long p = primes[idx];
        long value = current;
        while (value <= (limit - 1) / p) {
            value *= p;
            out.add(value);
            generateAdmissible(primes, idx + 1, value, limit, out);
        }
    }

    static int pseudoFortunate(long n) {
        for (int m = 3;; m += 2) {
            if (isPrime(n + m)) {
                return m;
            }
        }
    }

    public static String solve() {
        long limit = 1000000000L;
        Set<Long> admissible = new HashSet<>();
        int[] primes = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 };
        generateAdmissible(primes, 0, 1L, limit, admissible);

        Set<Integer> pseudoValues = new HashSet<>();
        for (long n : admissible) {
            pseudoValues.add(pseudoFortunate(n));
        }

        long sum = 0;
        for (int m : pseudoValues) {
            sum += m;
        }
        return String.valueOf(sum);
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}