Project Euler Problem 97

Solution

Answer: 8739992577

We need the last ten digits of

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

The key observation is that only the last ten digits matter, so we should compute everything modulo

$$10^{10}.$$

That is,

$$N \bmod 10^{10} = \left(28433 \times 2^{7830457} + 1\right)\bmod 10^{10}.$$

Instead of trying to compute $2^{7830457}$ directly (which is astronomically large), we use modular exponentiation.

Step 1: Modular arithmetic principle

For integers $a,b,m$,

$$(a\cdot b)\bmod m = ((a\bmod m)(b\bmod m))\bmod m.$$

Thus we can repeatedly reduce intermediate values modulo $10^{10}$.

We want:

$$2^{7830457}\pmod{10^{10}}.$$

The efficient way is binary exponentiation (also called fast exponentiation), which computes powers in $O(\log n)$ time.

Python provides this directly:

pow(base, exponent, modulus)

which computes

$$\text{base}^{\text{exponent}} \bmod \text{modulus}$$

efficiently without ever constructing the gigantic intermediate integer.

Python implementation

# Compute the last ten digits of:
# 28433 * 2^7830457 + 1

MOD = 10**10

# Efficient modular exponentiation
power_mod = pow(2, 7830457, MOD)

# Compute the final result modulo 10^10
result = (28433 * power_mod + 1) % MOD

print(result)

Code walkthrough

`MOD = 10**10`

We define the modulus:

MOD = 10**10

because we only care about the last ten digits.

`pow(2, 7830457, MOD)`

power_mod = pow(2, 7830457, MOD)

This computes:

$$2^{7830457}\bmod 10^{10}$$

using fast modular exponentiation.

Instead of creating a number with over two million digits, Python repeatedly squares and reduces modulo $10^{10}$.

Final modular computation

result = (28433 * power_mod + 1) % MOD

This evaluates:

$$(28433 \times 2^{7830457} + 1)\bmod 10^{10}.$$

The % MOD ensures we keep only the last ten digits.

Small sanity example

Suppose we wanted the last five digits of:

$$3\times2^{10}+1.$$

Since:

$$2^{10}=1024,$$

we get:

$$3\times1024+1=3073.$$

Modulo $100000$, the result remains $3073$, confirming the method behaves correctly on a manageable case.

Final verification

The number is odd because $2^{7830457}$ is even, multiplying by $28433$ remains even, and adding $1$ makes it odd.
Our final digits should therefore end in an odd number — a useful sanity check.
The computation uses exact modular arithmetic, so no precision loss occurs.

Answer: 8739992577