### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,183)
- misc (2)
- project euler (2)
- puzzle (46)
- site news (46)
- tantalizer (49)
- teaser (3)

### Site Stats

- 184,818 hits

Advertisements

Programming Enigma Puzzles

27 May 2015

Posted by on **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 7777777

^{7777777}?

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

[enigma1230]

Advertisements

%d bloggers like this:

Python’s built-in

pow()can compute problems like this directly. This Python program (statement) runs in 23ms.Solution:The last five digits of 7777777^{7777777}are 47697.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 calculatingmpow(A, B, M)directly).A variation on the same theme also appeared in

IBM Ponder This, October 2014In Mathematica, Print[PowerMod[7777777, 7777777, 100000]] also gives 47697 as the answer.