Problem 97: Large Non-Mersenne Prime

View on Project Euler

Project Euler Problem 97 Solution

EulerSolve provides an optimized solution for Project Euler Problem 97, Large Non-Mersenne Prime, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary The number in the problem is $$N=28433\cdot 2^{7830457}+1.$$ Writing out \(N\) in full would be pointless, because the question asks only for the last ten digits. That means we do not need \(N\) itself; we need only its residue modulo $$m=10^{10}.$$ So the whole task is to evaluate \(N \bmod m\). Once that modular computation is done, the final ten-digit residue is \(8739992577\). Mathematical Approach The C++, Python, and Java implementations all use the same mathematical reduction: keep every intermediate value modulo \(10^{10}\), compute the huge power with binary exponentiation, and then apply the outer multiplication by \(28433\) and the final \(+1\). Reduce the problem to one modular identity Because congruences respect multiplication and addition, we may reduce the power first: $$N \equiv 28433\cdot \left(2^{7830457}\bmod m\right)+1 \pmod m.$$ If we set $$P\equiv 2^{7830457}\pmod m,$$ then the answer is simply $$\boxed{(28433\cdot P+1)\bmod 10^{10}.}$$ So the real work is concentrated in one object: the residue of \(2^{7830457}\) modulo \(10^{10}\). Binary exponentiation gives the right recurrence The exponent \(7830457\) is large, but it has only 23 binary digits. Binary exponentiation processes that exponent by repeated halving....

Detailed mathematical approach

Problem Summary

The number in the problem is

$$N=28433\cdot 2^{7830457}+1.$$

Writing out \(N\) in full would be pointless, because the question asks only for the last ten digits. That means we do not need \(N\) itself; we need only its residue modulo

$$m=10^{10}.$$

So the whole task is to evaluate \(N \bmod m\). Once that modular computation is done, the final ten-digit residue is \(8739992577\).

Mathematical Approach

The C++, Python, and Java implementations all use the same mathematical reduction: keep every intermediate value modulo \(10^{10}\), compute the huge power with binary exponentiation, and then apply the outer multiplication by \(28433\) and the final \(+1\).

Reduce the problem to one modular identity

Because congruences respect multiplication and addition, we may reduce the power first:

$$N \equiv 28433\cdot \left(2^{7830457}\bmod m\right)+1 \pmod m.$$

If we set

$$P\equiv 2^{7830457}\pmod m,$$

then the answer is simply

$$\boxed{(28433\cdot P+1)\bmod 10^{10}.}$$

So the real work is concentrated in one object: the residue of \(2^{7830457}\) modulo \(10^{10}\).

Binary exponentiation gives the right recurrence

The exponent \(7830457\) is large, but it has only 23 binary digits. Binary exponentiation processes that exponent by repeated halving. Start with

$$r_0=1,\qquad b_0=2\bmod m,\qquad e_0=7830457.$$

At each step, if the current exponent is odd, multiply the accumulated result by the current base; then square the base and halve the exponent:

$$ \text{if } e_t \text{ is odd, then } r_{t+1}\equiv r_t b_t \pmod m,\quad \text{otherwise } r_{t+1}=r_t, $$

$$ b_{t+1}\equiv b_t^2\pmod m,\qquad e_{t+1}=\left\lfloor \frac{e_t}{2}\right\rfloor. $$

After about \(\lfloor \log_2 7830457 \rfloor+1=23\) iterations, the exponent becomes zero, so the algorithm finishes very quickly.

The loop invariant that proves correctness

The key invariant is

$$r_t\cdot b_t^{e_t}\equiv 2^{7830457}\pmod m.$$

Initially this is true because \(r_0=1\), \(b_0=2\), and \(e_0=7830457\). If \(e_t\) is odd, we move one factor of \(b_t\) from \(b_t^{e_t}\) into \(r_t\); if \(e_t\) is even, we do not need that extra multiplication. In both cases we then replace \(b_t\) by \(b_t^2\) and replace \(e_t\) by \(\lfloor e_t/2\rfloor\), which preserves the same total power of 2 modulo \(m\).

When the loop terminates, \(e_t=0\). The invariant becomes

$$r_t\equiv 2^{7830457}\pmod m,$$

so the accumulated value is exactly the residue we need.

Worked example with a reduced exponent

A smaller version of the same computation appears naturally as a checkpoint. Replace \(7830457\) by \(20\). Then

$$2^{20}=1048576,$$

so

$$28433\cdot 2^{20}+1=28433\cdot 1048576+1=29814161409.$$

Taking the last ten digits gives

$$29814161409\bmod 10^{10}=9814161409.$$

This is mathematically identical to the full problem. The only difference is that the real exponent is much larger, so repeated squaring is essential.

Why the solution stays with direct modular arithmetic

The modulus is

$$10^{10}=2^{10}\cdot 5^{10}.$$

Since the base is 2, we have \(\gcd(2,10^{10})=2\neq 1\). That means the usual form of Euler's theorem does not directly reduce the exponent modulo \(\varphi(10^{10})\) for the full modulus. The implementations therefore use the robust approach that always works: repeated squaring with modular reduction at every multiplication.

How the Code Works

Shared computational structure

All three implementations follow the same mathematical pipeline. First they set the modulus to \(10^{10}\). Next they compute the residue of \(2^{7830457}\) modulo that modulus. Then they multiply by \(28433\), add 1, reduce once more modulo \(10^{10}\), and print the resulting ten-digit tail.

Why the arithmetic layer differs by language

The mathematical formula is identical in C++, Python, and Java, but the arithmetic tools are different. The C++ implementation performs modular multiplication through a wider intermediate integer type, because the product of two residues below \(10^{10}\) can be as large as roughly \(10^{20}\), which does not fit safely in ordinary 64-bit multiplication. The Python implementation relies on built-in arbitrary-precision integers and built-in modular exponentiation. The Java implementation uses arbitrary-precision integer arithmetic together with the library operation for modular powers.

Sanity checks in the implementation

The C++ version also verifies the core arithmetic on two smaller cases before printing the final answer. One checkpoint confirms

$$2^{10}\equiv 24\pmod{1000},$$

and another confirms the reduced full-expression example

$$28433\cdot 2^{20}+1\equiv 9814161409\pmod{10^{10}}.$$

Those checks reflect the same recurrence and the same final formula used for the actual exponent \(7830457\).

Complexity Analysis

Binary exponentiation uses \(O(\log e)\) modular multiplications, where \(e=7830457\). Since \(e\) has only 23 binary digits, the main loop runs only about 23 iterations, with at most one extra modular multiplication in each iteration when the current bit is 1.

The memory usage is \(O(1)\) in the mathematical sense: the algorithm stores only a fixed number of integers such as the current result, the current base, the current exponent, and the modulus. Even in the arbitrary-precision implementations, every value is immediately reduced modulo \(10^{10}\), so the integers remain tiny compared with the full size of \(N\).

Footnotes and References

  1. Problem page: https://projecteuler.net/problem=97
  2. Modular arithmetic: Wikipedia - Modular arithmetic
  3. Modular exponentiation: Wikipedia - Modular exponentiation
  4. Exponentiation by squaring: Wikipedia - Exponentiation by squaring
  5. Proth number: Wikipedia - Proth number

Problem 97 source code

C++

#include <cstdint>
#include <iostream>
#include <string>

namespace {

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

struct Options {
    u64 coefficient = 28433ULL;
    u64 base = 2ULL;
    u64 exponent = 7830457ULL;
    u64 increment = 1ULL;
    u64 mod = 10000000000ULL;
    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 = 0;
    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, "--coefficient=", options.coefficient) ||
            parse_u64_after_prefix(arg, "--base=", options.base) ||
            parse_u64_after_prefix(arg, "--exponent=", options.exponent) ||
            parse_u64_after_prefix(arg, "--increment=", options.increment) ||
            parse_u64_after_prefix(arg, "--mod=", options.mod)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }

    return options.mod > 0;
}

u64 mul_mod(const u64 a, const u64 b, const u64 mod) {
    return static_cast<u64>((static_cast<u128>(a) * static_cast<u128>(b)) % mod);
}

u64 pow_mod(u64 base, u64 exponent, const u64 mod) {
    u64 result = 1ULL % mod;
    base %= mod;

    while (exponent > 0) {
        if ((exponent & 1ULL) != 0ULL) {
            result = mul_mod(result, base, mod);
        }
        base = mul_mod(base, base, mod);
        exponent >>= 1ULL;
    }

    return result;
}

u64 solve(const u64 coefficient, const u64 base, const u64 exponent, const u64 increment, const u64 mod) {
    const u64 power = pow_mod(base, exponent, mod);
    const u64 scaled = mul_mod(coefficient % mod, power, mod);
    return (scaled + increment % mod) % mod;
}

bool run_checkpoints() {
    if (pow_mod(2ULL, 10ULL, 1000ULL) != 24ULL) {
        std::cerr << "Checkpoint failed for modular exponentiation" << '\n';
        return false;
    }

    const u64 small = solve(28433ULL, 2ULL, 20ULL, 1ULL, 10000000000ULL);
    if (small != 9814161409ULL) {
        std::cerr << "Checkpoint failed for reduced exponent scenario" << '\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.coefficient, options.base, options.exponent, options.increment, options.mod) << '\n';
    return 0;
}

Python

# Problem 97: Large non-Mersenne prime
# Find the last ten digits of 28433 * 2^7830457 + 1.

def solve():
    mod = 10**10
    print((28433 * pow(2, 7830457, mod) + 1) % mod)

solve()

Java

import java.math.BigInteger;

public class Euler97 {
    public static void main(String[] args) {
        BigInteger mod = BigInteger.TEN.pow(10);
        BigInteger result = BigInteger.valueOf(28433).multiply(BigInteger.TWO.modPow(BigInteger.valueOf(7830457), mod))
                .add(BigInteger.ONE).mod(mod);
        System.out.println(result);
    }
}