### Random Post

### Recent Posts

- Enigma 1084: 1-2-3 triangles
- Tantalizer 466: Diplomacy
- Tantalizer 467: Nine men went to mow
- Enigma 1085: Cut and run
- Enigma 425: Them thar’ Hills
- Puzzle 60: Uncle Bungle gets the last line wrong
- Enigma 1086: Stacking trays
- Enigma 424: A round of fractions
- Tantalizer 468: Shell fire
- Enigma 1087: Egyptian triangles

### Recent Comments

Jim Randell on Enigma 1084: 1-2-3 triang… | |

Brian Gladman on Enigma 1084: 1-2-3 triang… | |

Jim Randell on Enigma 1084: 1-2-3 triang… | |

geoffrounce on Enigma 1631: Joe’s … | |

geoffrounce on Enigma 1626: Pascal’s… |

### Archives

### Categories

- article (11)
- enigma (1,128)
- misc (2)
- project euler (2)
- puzzle (32)
- site news (43)
- tantalizer (34)
- teaser (3)

### Site Stats

- 169,890 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.