# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1230: High power

From New Scientist #2386, 15th March 2003 [link]

George and his son are considering the powers of numbers.

“What is 7 to the power 7, Son?”

“My 10-digit calculator says it’s 823543.”

“Can it calculate 7777777 to the power 7777777?”

“You must be joking, Dad. That number must have millions of digits.”

“53,595,538 digits, to be precise, but the last five will do.”

What are the last five digits of 77777777777777?

Enigma 1494 and Enigma 1731 are also about computing powers modulo some number.

[enigma1230]

### 4 responses to “Enigma 1230: High power”

1. Jim Randell 27 May 2015 at 7:16 am

Python’s built-in pow() can compute problems like this directly. This Python program (statement) runs in 23ms.

```print(pow(7777777, 7777777, 100000))
```

Solution: The last five digits of 77777777777777 are 47697.

• Jim Randell 27 May 2015 at 7:17 am

The problem is similar to Enigma 1494. Here’s a program that uses Euler’s Theorem [ http://en.wikipedia.org/wiki/Euler%27s_theorem ] to reduce the exponent and then use repeated squaring to calculate the result in 15 iterations (rather than 23 iterations for calculating mpow(A, B, M) directly).

```from enigma import prime_factor, printf

def phi(n):
t = n
for (p, _) in prime_factor(n):
t -= t // p
return t

def mpow(a, b, n):
s = 1
while b > 0:
(b, r) = divmod(b, 2)
if r > 0: s = (s * a) % n
a = (a * a) % n
return s

A = B = 7777777
M = 100000

p = phi(M)
q = B % p

r = mpow(A, q, M)

printf("{A}^{B} mod {M} = {r} [phi({M})={p}, {B} mod {p}={q}]")
```
2. arthurvause 27 May 2015 at 8:27 am

A variation on the same theme also appeared in IBM Ponder This, October 2014

• geoffrounce 27 May 2015 at 4:27 pm

In Mathematica, Print[PowerMod[7777777, 7777777, 100000]] also gives 47697 as the answer.