## Square Digit Chains

### October 19, 2018

Today’s task appears on Project Euler, Rosetta Code, and Sloane’s, so it is well worth a look; we even did a version of this task in a previous exercise. Here is the Project Euler version of the problem:

A number chain is created by continuously added the square of the digits of a number to form a new number until it has been seen before. For example:

44 → 32 → 13 → 10 → 1 → 1

85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89

Therefore any chain that arrives at 1 or 89 will become stuck in an endless loop. What is most amazing is that EVERY starting number will eventually arrive at 1 or 89.

How many starting numbers below ten million will arrive at 89?

Your task is to write a program to find the count of starting numbers below ten million that arrive at 89, following the usual Project Euler rule that your computation may take no more than a minute of computation on a recent-vintage personal computer. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

In Python.

The solution of ProgrammingPraxis in Python. This is indeed a lot faster than my solution.

At most we have 7 digits. The range of the sumsq of the digits will be 1…567 (7.9^2). Thus every

sumsq yields a value in [1, 567]. So first we calculate the chains for 1…567 storing the result

in table[]. Thereafter we calculate sumsq(n), n > 567, and increment count if table[sumsq[n]) = 89.

Answer 8581146 0.35 sec

A brute force solution in cpp

I’d just like to mention that, although it’s of course admirable to simplify by developing a permutations based solution, doing a full check on 10,000,000 numbers took about half a second on my current desktop. Maybe I’m not clear on what a “recent-vintage personal computer” is meant to encompass, but it doesn’t need to be optimized if it meets the requirements of the problem. :)

Here’s a nice way to solve the problem (I took the basic idea from the first C solution on the Rosetta code page): define a function count(n,m) that gives the number of n digit numbers (including leading zeros) that have a square digit sum of m – this has a fairly simple recursive formulation that by itself is rather inefficient but can be improved dramatically by memoizing its arguments (alternatively we can use a dynamic programming approach, see the above mentioned C solution for details). With Python’s bignums we can easily count all the 20 digit (or more) numbers with iterated square sum of 89:

Klong and Mumps solutions

Run:

Klong 20180213

]l lib/steve2.kg

loading “./lib/steve2.kg”

num::9999999; .sys(“date”); chsumsq(num); .sys(“date”)

Tue Oct 23 15:03:11 PDT 2018

Starting numbers arriving at 89: 4006299

Tue Oct 23 15:35:58 PDT 2018

0

===

Run:

s secs=$p($h,”,”,2) x loop w !!,”sum = “,sum,!!,”Seconds = “,$p($h,”,”,2)-secs

iterations: 9999999

sum = 4006299

Seconds = 101

Here’s a solution in C. On my desktop it takes about 0.30 seconds without compiler optimizations and 0.10 seconds with -O2.

Output:

Here’s a nice variation on the combinations method: generate the combinations explicitly, but at the same time keep track of the digit sum and factorials, adjusting them as we go:

Not as fast as previous solution, but gets up to 20 digits in a minute or two:

Wow. The official solution put in a lot of effort. I just slapped some memoization into a simplistic approach and called it acceptable. The added restriction of one minute compute time seemed a bit silly. https://ideone.com/9xi2dd