Enigmatic Code

Programming Enigma Puzzles

Enigma 1230: High power

From New Scientist #2386, 15th March 2003 [link]

George and his son are considering the powers of numbers.

“What is 7 to the power 7, Son?”

“My 10-digit calculator says it’s 823543.”

“Can it calculate 7777777 to the power 7777777?”

“You must be joking, Dad. That number must have millions of digits.”

“53,595,538 digits, to be precise, but the last five will do.”

What are the last five digits of 77777777777777?

Enigma 1494 and Enigma 1731 are also about computing powers modulo some number.

[enigma1230]

Advertisements

4 responses to “Enigma 1230: High power

  1. Jim Randell 27 May 2015 at 7:16 am

    Python’s built-in pow() can compute problems like this directly. This Python program (statement) runs in 23ms.

    print(pow(7777777, 7777777, 100000))
    

    Solution: The last five digits of 77777777777777 are 47697.

    • Jim Randell 27 May 2015 at 7:17 am

      The problem is similar to Enigma 1494. Here’s a program that uses Euler’s Theorem [ http://en.wikipedia.org/wiki/Euler%27s_theorem ] to reduce the exponent and then use repeated squaring to calculate the result in 15 iterations (rather than 23 iterations for calculating mpow(A, B, M) directly).

      from enigma import prime_factor, printf
      
      def phi(n):
        t = n
        for (p, _) in prime_factor(n):
          t -= t // p
        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
       
      A = B = 7777777
      M = 100000
       
      p = phi(M)
      q = B % p
       
      r = mpow(A, q, M)
       
      printf("{A}^{B} mod {M} = {r} [phi({M})={p}, {B} mod {p}={q}]")
      
  2. arthurvause 27 May 2015 at 8:27 am

    A variation on the same theme also appeared in IBM Ponder This, October 2014

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: