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]

Advertisements

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}]")
    

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: