Enigmatic Code

Programming Enigma Puzzles

Enigma 1494: Powerful logic

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:

3123456

What are they?

[enigma1494]

2 responses to “Enigma 1494: Powerful logic”

1. Jim Randell 10 November 2012 at 11:05 pm

Python has 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).

```from enigma import irange, printf

N = 123456

# the simple way: 4.6ms
s = pow(3, N) % 1000
printf("3^{N} = ...{s}")

# the quick way: 0.819us (0.0011us with pypy)
s = pow(3, N, 1000)
printf("3^{N} = ...{s}")

# the slow way: 13.9ms (2.2ms with pypy)
def mpow1(a, b, n):
s = 1
for i in irange(1, b):
s = (s * a) % n
return s

s = mpow1(3, N, 1000)
printf("3^{N} = ...{s}")

# the binary way: 8.8us (0.476us with pypy)
def mpow2(a, b, n):
s = 1
while b > 0:
(b, r) = divmod(b, 2)
if r > 0: s = (s * a) % n
a = (a * a) % n
return s

s = mpow2(3, N, 1000)
printf("3^{N} = ...{s}")
```

Solution: The last three digits are 521.

2. Jim Randell 12 January 2013 at 12:13 am

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.

```from enigma import factor, printf

def phi(n):
t = n
for k in set(factor(n)):
t -= t // k
return t

def mpow(a, b, n):
s = 1
while b > 0:
(b, r) = divmod(b, 2)
if r > 0: s = (s * a) % n
a = (a * a) % n
return s

N = 123456
M = 1000

p = phi(M)
q = N % p

r = mpow(3, q, M)

printf("3^{N} mod {M} = {r} [phi({M})={p}, {N} mod {p}={q}]")
```

This site uses Akismet to reduce spam. Learn how your comment data is processed.