Enigmatic Code

Programming Enigma Puzzles

Enigma 1561: Some check!

From New Scientist #2724, 5th September 2009 [link]

Joe has been teaching Penny all about “checksums”, which have been used for years to check the accuracy of calculations.

To calculate the checksum of a number you add up its digits. If that total is a single digit then that is the checksum; if not, the digits in the total are added to produce a new total and the process is repeated until a single-digit answer is produced. That single digit is the original number’s checksum.

What is the checksum of the number (2100 + 3200)300?

[enigma1561]

Advertisements

5 responses to “Enigma 1561: Some check!

  1. jimrandell 22 February 2012 at 2:00 pm

    There are several properties of Digital Roots that can be used to simplify this problem.

    But Python, with its arbitrarily large integers, is more than happy to tackle the problem head on. The following program runs in 98ms.

    from enigma import printf
    
    def checksum(n):
      while n > 9:
        s = str(n)
        r = sum(int(d) for d in s)
        printf("[{s} => {r}]")
        n = r
      return n
    
    import sys
    n = ((2 ** 100) + (3 ** 200)) ** 300 if len(sys.argv) < 2 else eval(sys.argv[1])
    
    print(checksum(n))
    

    Solution: The checksum is 1.

  2. Greg 23 February 2012 at 6:49 pm

    I used reduce() with a lambda and recursion:

    def checksum(num):
    	combo = reduce(lambda x, y: int(x) + int(y), str(num))
    	return checksum(combo) if combo > 9 else combo
    print checksum(((2 ** 100) + (3 ** 200)) ** 300)
    

    got about the same performance.

    • Jim Randell 24 February 2012 at 10:00 am

      I think any solution that creates the huge integer, converts it to a decimal string and then operates on that is going to find that the lions share of the time goes into dealing with the large integer.

      And it seems pointless to optimise a program that runs in less than 100ms, but… if computing digital roots was more expensive, or if you didn’t have a nice friendly language that deals with 28,628 digit numbers without breaking a sweat you could use some of the identities of the digital root function to reduce the size of the numbers you’re dealing with.

      This program never has to calculate digital roots of numbers larger than two digits (you could even precompute or cache the results) and it runs in 32ms, which I think is pretty much the start-up time for Python anyway. It also avoids converting numbers into strings. (I’ve renamed checksum to D to save typing):

      def D(n):
        print(n)
        while n > 9 :
          n = sum(divmod(n, 10))
        return n
      
      # D(a + b) = D(D(a) + D(b))
      def plus(a, b):
        return D(D(a) + D(b))
      
      # D(a * b) = D(D(a) * D(b))
      def mul(a, b):
        return D(D(a) * D(b))
      
      # D(a^n) = pD(a, n) = D(D(a) * pD(a, n-1))
      def power(a, n):
        if n == 1: return D(a)
        return D(D(a) * power(a, n-1))
      
      print(power(plus(power(2, 100), power(3, 200)), 300))
      
      • Jim Randell 24 February 2012 at 11:44 am

        You can even run this version on the BBC Micro (via the excellent BeebEm3 emulator) in less than 10s (without increasing the emulated speed). Although, because of the heavy recursion, it only runs in MODE 7 (other MODEs consume too much memory for their bitmapped display).

        >LIST
           10 start% = TIME
           20 PRINT "checksum = ";FNpower(FNplus(FNpower(2, 100), FNpower(3, 200)), 300)
           30 PRINT "Time = ";(TIME - start%) / 100;"s"
           40 END
           50 DEF FND(n%)
           60   REPEAT 
           70     n% = (n% DIV 10) + (n% MOD 10)
           80   UNTIL n% < 10
           90   =n%
          100 DEF FNplus(a%, b%)=FND(FND(a%) + FND(b%))
          110 DEF FNmul(a%, b%)=FND(FND(a%) * FND(b%))
          120 DEF FNpower(a%, n%)
          130   IF n% = 1 THEN =FND(a%)
          140   =FND(FND(a%) * FNpower(a%, n% - 1))    
        
        >MODE 7
        >RUN
        checksum = 1
        Time = 11.99s
        
        >MODE 3
        >RUN
        checksum = 
        No room at line 140
        

        We can reduce the amount of recursion by handling squares in FNpower (see line 135), then the program runs fine in other MODEs (and is a lot faster).

        >LIST
           10 start% = TIME
           20 PRINT "checksum = ";FNpower(FNplus(FNpower(2, 100), FNpower(3, 200)), 300)
           30 PRINT "Time = ";(TIME - start%) / 100;"s"
           40 END
           50 DEF FND(n%)
           60   REPEAT 
           70     n% = (n% DIV 10) + (n% MOD 10)
           80   UNTIL n% < 10
           90   =n%
          100 DEF FNplus(a%, b%)=FND(FND(a%) + FND(b%))
          110 DEF FNmul(a%, b%)=FND(FND(a%) * FND(b%))
          120 DEF FNpower(a%, n%)
          130   IF n% = 1 THEN =FND(a%)
          135   IF n% MOD 2 = 0 THEN =FND(FNpower(a%, n% DIV 2) ^ 2)
          140   =FND(FND(a%) * FNpower(a%, n% - 1))    
        
        >MODE 3
        >RUN
        checksum = 1
        Time = 0.61s
        

        A similar addition to the Python program above reduces the execution from 3110 function calls to 132 function calls (according to cProfile) – although it still executes in 32ms.

        Of course further mathematical analysis shows that the digital root of increasing powers of 2 result in the repeating sequence: 2, 4, 8, 7, 5, 1, …, for powers of 7 the repeating sequence is: 7, 4, 1, … and that any multiple of 9 has a digital root of 9, hence any large power of 3 has a digital root of 9.

        So: D(2^100) = 7 (as 100 mod 6 = 4 and 7 is the 4th element in the repeating sequence for powers of 2), and D(3^200) = 9. So D(2^100 + 3^200) = D(D(2^100) + D(3^200)) = D(7+9) = 7. And D(7^300) = 1 (as 300 mod 3 = 0 and 1 is the 3rd element in the repeating sequence for powers of 7).

        Hence the answer to whole question is 1, without bignums, recursion or even a computer. But it’s not as fun.

  3. Jim Randell 23 March 2014 at 2:42 pm

    I added a function to the enigma.py library to compute digital roots. The code for it looks like this:

    def digrt(n):
      return (0 if n == 0 else int(1 + (n - 1) % 9))
    

    Using this routine the program becomes:

    from enigma import digrt
    
    print(digrt(((2 ** 100) + (3 ** 200)) ** 300))
    

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: