Square Digit Chains
October 19, 2018
We begin with a simple program to display one chain:
(define (sdc n) (cond ((member n '(1 89)) n) (else (display n) (display #\space) (sdc (sum (map square (digits n))))))) > (sdc 44) 44 32 13 10 1 > (sdc 145) 145 42 20 4 16 37 58 89
We could invoke that program ten million times, but it wouldn’t finish in any reasonable time. Instead, we observe that 1234567 and 7654321, and indeed any permutation of those seven digits, will lead to the same square digit chain, so we only have to compute the canonical form of all the permutations less than ten million, compute the number of permutations for each canonical form that leads to 89, and add them up:
(define (euler92) (define (sdc n) (if (member n '(0 1 89)) n (sdc (sum (map square (digits n)))))) (define (perms xs) (define (fact n) (apply * (range n 0))) (let loop ((p (fact (length xs))) (freq (uniq-c = xs))) (if (null? freq) p (loop (/ p (fact (cdar freq))) (cdr freq))))) (fold-of + 0 p (a range 0 10) (b range a 10) (c range b 10) (d range c 10) (e range d 10) (f range e 10) (g range f 10) (n is (list a b c d e f g)) (= (sdc (undigits n)) 89) (p is (perms n)))) > (time (euler92)) (time (euler92)) 2 collections 0.038801653s elapsed cpu time, including 0.000115820s collecting 0.038834982s elapsed real time, including 0.000122825s collecting 20564512 bytes allocated, including 16846320 bytes reclaimed 8581146
There are 11,440 canonical forms, of which 9814 lead to 89. You can run the program at https://ideone.com/w1QtD8.
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