### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,123)
- misc (2)
- project euler (2)
- puzzle (31)
- site news (43)
- tantalizer (31)
- teaser (3)

### Site Stats

- 168,282 hits

Programming Enigma Puzzles

22 February 2012

Posted by on **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 (2

^{100}+ 3^{200})^{300}?

[enigma1561]

Advertisements

%d bloggers like this:

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.

Solution:The checksum is 1.I used reduce() with a lambda and recursion:

got about the same performance.

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

checksumtoDto save typing):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).We can reduce the amount of recursion by handling squares in

FNpower(see line135), then the program runs fine in otherMODEs (and is a lot faster).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.

I added a function to the

enigma.pylibrary to compute digital roots. The code for it looks like this:Using this routine the program becomes: