Problem #97 easy

Large non-Mersenne prime

The first known prime found to exceed one million digits was discovered in 1999, and is a Mersenne prime of the form $2^{6972593} - 1$ ; it contains exactly $2\,098\,960$ digits. Subsequently other Mersenne primes, of the form $2^p - 1$ , have been found which contain more digits.

However, in 2004 there was found a massive non-Mersenne prime which contains $2\,357\,207$ digits: $28433 \times 2^{7830457} + 1$ .

Find the last ten digits of this prime number.

View on Project Euler

Implementations

#include <iostream>

long long mod_pow(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1) {
            // Use __int128 to avoid overflow in multiplication
            __int128 temp = (__int128)result * base % mod;
            result = temp;
        }
        __int128 temp_base = (__int128)base * base % mod;
        base = temp_base;
        exp /= 2;
    }
    return result;
}

long long large_non_mersenne_prime() {
    const long long MOD = 10000000000LL; // 10^10
    long long pow2 = mod_pow(2, 7830457, MOD);
    // Use __int128 for the final multiplication to avoid overflow
    __int128 temp = (__int128)28433LL * pow2 % MOD;
    long long result = (temp + 1) % MOD;
    return result;
}

View on GitHub

~1ms

package main

func modPow(base, exp, mod int64) int64 {
    result := int64(1)
    base %= mod
    for exp > 0 {
        if exp%2 == 1 {
            result = (result * base) % mod
        }
        base = (base * base) % mod
        exp /= 2
    }
    return result
}

func largeNonMersennePrime() int64 {
    const MOD int64 = 10000000000
    pow2 := modPow(2, 7830457, MOD)
    result := (28433 * pow2 % MOD + 1) % MOD
    return result
}

View on GitHub

~1ms

public class Euler097 {
    static long modPow(long base, long exp, long mod) {
        long result = 1;
        base %= mod;
        while (exp > 0) {
            if (exp % 2 == 1) {
                result = (result * base) % mod;
            }
            base = (base * base) % mod;
            exp /= 2;
        }
        return result;
    }

    static long largeNonMersennePrime() {
        final long MOD = 10000000000L;
        long pow2 = modPow(2, 7830457, MOD);
        long result = (28433L * pow2 % MOD + 1) % MOD;
        return result;
    }
}

View on GitHub

~1ms

function large_non_mersenne_prime() {
  const base = 28433n;
  const exp = 7830457n;
  const mod = 10000000000n;
  let result = 1n;
  let b = 2n; // base for exponentiation is 2
  let e = exp;
  while (e > 0n) {
    if (e % 2n === 1n) result = (result * b) % mod;
    b = (b * b) % mod;
    e /= 2n;
  }
  // Now result is 2^exp % mod
  result = (result * (base % mod)) % mod;
  result = (result + 1n) % mod;
  return Number(result);
}

View on GitHub

~1ms

def solve():
    base = 28433
    exp = 7830457
    mod = 10**10
    result = pow(2, exp, mod) * base % mod + 1
    return result

View on GitHub

~1ms

pub fn large_non_mersenne_prime() -> String {
    let base = 28433u64;
    let exp = 7830457u32;
    let modulus = 10_000_000_000u64;
    let pow = mod_pow(2, exp, modulus);
    let result = (base as u128 * pow as u128 % modulus as u128 + 1) % modulus as u128;
    format!("{:010}", result)
}

fn mod_pow(mut base: u64, mut exp: u32, modulus: u64) -> u64 {
    let mut result = 1u64;
    base %= modulus;
    while exp > 0 {
        if exp % 2 == 1 {
            result = ((result as u128 * base as u128) % modulus as u128) as u64;
        }
        base = ((base as u128 * base as u128) % modulus as u128) as u64;
        exp /= 2;
    }
    result
}

View on GitHub

~1ms

#include <iostream>

long long mod_pow(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1) {
            // Use __int128 to avoid overflow in multiplication
            __int128 temp = (__int128)result * base % mod;
            result = temp;
        }
        __int128 temp_base = (__int128)base * base % mod;
        base = temp_base;
        exp /= 2;
    }
    return result;
}

long long large_non_mersenne_prime() {
    const long long MOD = 10000000000LL; // 10^10
    long long pow2 = mod_pow(2, 7830457, MOD);
    // Use __int128 for the final multiplication to avoid overflow
    __int128 temp = (__int128)28433LL * pow2 % MOD;
    long long result = (temp + 1) % MOD;
    return result;
}

View on GitHub

~1ms

package main

func modPow(base, exp, mod int64) int64 {
    result := int64(1)
    base %= mod
    for exp > 0 {
        if exp%2 == 1 {
            result = (result * base) % mod
        }
        base = (base * base) % mod
        exp /= 2
    }
    return result
}

func largeNonMersennePrime() int64 {
    const MOD int64 = 10000000000
    pow2 := modPow(2, 7830457, MOD)
    result := (28433 * pow2 % MOD + 1) % MOD
    return result
}

View on GitHub

~1ms

public class Euler097 {
    static long modPow(long base, long exp, long mod) {
        long result = 1;
        base %= mod;
        while (exp > 0) {
            if (exp % 2 == 1) {
                result = (result * base) % mod;
            }
            base = (base * base) % mod;
            exp /= 2;
        }
        return result;
    }

    static long largeNonMersennePrime() {
        final long MOD = 10000000000L;
        long pow2 = modPow(2, 7830457, MOD);
        long result = (28433L * pow2 % MOD + 1) % MOD;
        return result;
    }
}

View on GitHub

~1ms

function large_non_mersenne_prime() {
  const base = 28433n;
  const exp = 7830457n;
  const mod = 10000000000n;
  let result = 1n;
  let b = 2n; // base for exponentiation is 2
  let e = exp;
  while (e > 0n) {
    if (e % 2n === 1n) result = (result * b) % mod;
    b = (b * b) % mod;
    e /= 2n;
  }
  // Now result is 2^exp % mod
  result = (result * (base % mod)) % mod;
  result = (result + 1n) % mod;
  return Number(result);
}

View on GitHub

~1ms

def solve():
    base = 28433
    exp = 7830457
    mod = 10**10
    result = pow(2, exp, mod) * base % mod + 1
    return result

View on GitHub

~1ms

pub fn large_non_mersenne_prime() -> String {
    let base = 28433u64;
    let exp = 7830457u32;
    let modulus = 10_000_000_000u64;
    let pow = mod_pow(2, exp, modulus);
    let result = (base as u128 * pow as u128 % modulus as u128 + 1) % modulus as u128;
    format!("{:010}", result)
}

fn mod_pow(mut base: u64, mut exp: u32, modulus: u64) -> u64 {
    let mut result = 1u64;
    base %= modulus;
    while exp > 0 {
        if exp % 2 == 1 {
            result = ((result as u128 * base as u128) % modulus as u128) as u64;
        }
        base = ((base as u128 * base as u128) % modulus as u128) as u64;
        exp /= 2;
    }
    result
}

View on GitHub

~1ms

Solution Notes

Mathematical Background

The problem requires finding the last 10 digits of a very large number: 28433 × 2^7830457 + 1. Direct computation is impossible due to the number’s size, so modular arithmetic is used.

Algorithm Analysis

Compute 2^7830457 mod 10^10 using fast modular exponentiation (O(log exponent)), then multiply by 28433 mod 10^10, add 1, and take mod 10^10 again.

Performance

Extremely fast (~1ms) across all languages due to logarithmic time complexity and small modulus.

Key Insights

Modular exponentiation prevents overflow by taking remainders at each step
Big integer libraries needed in some languages for intermediate calculations
Last digits computation reduces huge number to manageable arithmetic

Educational Value

Demonstrates modular arithmetic applications, fast exponentiation algorithms, and handling very large numbers in programming.

Problem #97 is taken from Project Euler and licensed under CC BY-NC-SA 4.0.