### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,158)
- misc (2)
- project euler (2)
- puzzle (40)
- site news (44)
- tantalizer (42)
- teaser (3)

### Site Stats

- 178,002 hits

Advertisements

Programming Enigma Puzzles

10 November 2012

Posted by on **From New Scientist #2656, 17th May 2008**

Joe found this problem in one of his old maths books and gave it to Penny to solve. But as there was no solution in the book, Joe programmed his computer to find the answer and check Penny’s. All Penny had to do was find the last three digits of:

3

^{123456}What are they?

[enigma1494]

Advertisements

%d bloggers like this:

Python has builtin bigints, so you could just compute

pow(3, 123456) % 1000directly. However, the Pythonpow()function takes an optional third argument that does exactly what you need, so you can just callpow(3, 123456, 1000)to get the answer. This must be the shortest Python program I’ve written to solve an Enigma puzzle: 18 characters.The following Python code gets the (same) answer in four different ways. (Timings are taken using the Python

timeitmodule).Solution:The last three digits are 521.Here’s another approach that uses Euler’s Theorem to reduce the exponent from 123456 to 256, it then uses the “repeated squaring” algorithm (as above) to calculate the answer in 8 iterations.