### Random Post

### Recent Posts

- Enigma 415: Buses galore
- Puzzle 65: Division: figures all wrong
- Enigma 1097: Chessboard triangles
- Enigma 414: Nicely bungled, Sir!
- Tantalizer 473: Pigeon post
- Enigma 1098: Soccer heroes
- Enigma 413: Quargerly dues
- Puzzle 66: Hopes and successes on the island
- Enigma 1099: Unconnected cubes
- Enigma 412: A triangular square

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,106)
- misc (2)
- project euler (2)
- puzzle (27)
- site news (43)
- tantalizer (27)
- teaser (3)

### Site Stats

- 164,347 hits

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.