### Random Post

### Recent Posts

- Enigma 1109: All square in games
- Enigma 402: A DIY puzzle
- Puzzle 71: All wrong, all wrong
- Enigma 1110: Dots and lines
- Enigma 400: Potential difficulties
- Tantalizer 479: Cat and five tales
- Enigma 1111: Base-age
- Enigma 399: Time, gentlemen, please
- Tantalizer 480: Pitter patter
- Enigma 1112: Patio zones

### Recent Comments

Jim Randell on Enigma 1653: Cut-free | |

Jim Randell on Enigma 1109: All square in… | |

Jim Randell on Enigma 402: A DIY puzzle | |

geoffrounce on Puzzle 71: All wrong, all… | |

Jim Randell on Puzzle 71: All wrong, all… |

### Archives

### Categories

- article (11)
- enigma (1,080)
- misc (2)
- project euler (2)
- puzzle (21)
- site news (42)
- tantalizer (21)
- teaser (3)

### Site Stats

- 157,134 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.