# 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]

### 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)
```

• 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))
```