### Random Post

### Recent Posts

### Recent Comments

Jim Randell on Enigma 544a: Merry Christ… | |

Jim Randell on Puzzle #52: Bus change | |

J. Pijnenburg on Puzzle #52: Bus change | |

Jim Randell on Puzzle #53: Painting by n… | |

GeoffR on Puzzle #52: Bus change |

### Archives

### Categories

- article (11)
- enigma (1,367)
- misc (4)
- project euler (2)
- puzzle (90)
- puzzle# (48)
- site news (58)
- tantalizer (93)
- teaser (7)

### Site Stats

- 233,055 hits

Pythonhas builtin bigints, so you could just compute [[`pow(3, 123456) % 1000`

]] directly. However, the Python [[`pow()`

]] function takes an optional third argument that does exactly what you need, so you can just call [[`pow(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 [[

`timeit`

]] module).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.