 Project Euler 92: Investigating a square digits number chain with a surprising property.

Problem 92 of Project Euler is one of the more solve puzzles in this range, so based on that parameter this should be a pretty easy thing to chew through. The problem text reads

A number chain is created by continuously adding the square of the digits in 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?

I have found two methods to solve this. One where we  go through all 10.000.000 numbers to check what their cycle will be with a bit of help from some caching. And then a method where we exploit the fact that the order of the digits doesn’t matter and that significantly reduces the cases we need to check.

Brute Force

The first method we shall look at is a simple method where we will go through all 10.000.000 numbers to figure out their chain. However, we can still take a bit of a shortcut since we don’t have to go through the complete chain every time. We can store the result of already calculated numbers. In the example we can see that 44 leads to 1, so if we arrive at 44 there is no reason go through the last 4 jumps to figure the end result.

However, in order to do this it is nice to recognize that with 7 digit numbers the maximum second number in the chain is 92*7=567. So we don’t really need that big a cache in order to do this. I made the code a bit more generic so we don’t limit us self to a specific target size, but all in all the code is really simple

int result = 0;
int target = 10000000;
int cachesize = (int)Math.Ceiling(81 * Math.Log10(target))+1;
bool[] cache = new bool[cachesize+1];

for (int i = 1; i < cachesize; i++) {
int sequence = nextNumber(i);
while (sequence > i && sequence != 89) {
sequence = nextNumber(sequence);
}

if (cache[sequence] || sequence == 89) {
result++;
cache[i] = true;
}
}

for (int i = cachesize; i <= target; i++) {
if (cache[nextNumber(i)]) {
result++;
}
}

Furthermore I have a method for calculating the next number in the sequence

private int nextNumber(int input) {
int retVal = 0;

while (input > 0) {
int digit = input % 10;
retVal += digit * digit;
input /= 10;
}

return retVal;
}

I tried to precalculate the squares as well, but this method was faster on my computer. This is all, and it runs like this

There are 8581146 numbers that ends in 89
Solution took 822,2844 ms

Not really an acceptable run time and it scales poorly. So since I had the ideas for another solution approach I couldn’t accept this method.

Combinatorics approach

This approach utilizes that there are multiple numbers which give equal results. As an example 13 gives the same result as 31, 103, 130, 301, 310 and so on. This can be exploited a lot.  I will ignore the number 10.000.000 which clearly gives one and the assume that all numbers have 7 digits. That means some numbers have leading zeros.

This is also the downside of this method. I need to treat all numbers with a certain number of digits  in order to calculate the number of combinations I can make out them.

Let us look at the permutations of a given number. If the numbers are all distinct we would have N! permutations for an N digit number. However if 2 or more of the digits are the same we can’t distinguish between the two permutations and therefore we need to use the multinomial coefficient which states that the number of permutations of a multiset is

where A is the number of zeros, b is the number of ones and so on. So if we have figured out that a given number ends in 89, then we know that there are this amount of permutations more that gives the exact same result.

Next thing is to generate all the different multisets but none of them more than ones. In order to go this I assume that I have a number abcdefg such that a≤b≤c≤d≤e≤f≤g.  That with all zeros and then increase g one by one until we reach 9, then increase f to one and set g to one and increase it again.

The code for doing this generic is pretty similar to the approach of generating all combinations as we took in Problem 90. Something which looks complicated, but it is just a lot of logic to move back and forth in the array

int result = 0;
int target = 10000000;
int cachesize = (int)Math.Ceiling(Math.Log10(target));
int[] number = new int[cachesize];
int i = cachesize-1;

while (true) {
if (i == 0 && number[i] == 9){
//Reached max
break;
}
if (i == cachesize - 1 && number[i] < 9) {
//Increase the last number
number[i]++;
result += CheckNumber(number);
} else if (number[i] == 9) {
//we reach max, so move back
i--;
} else{
//Increase a digit
number[i]++;
//Move to the end
for (int j = i+1; j < cachesize; j++) {
number[j] = number[i];
}
i = cachesize - 1;
result += CheckNumber(number);
}
}

By trial and error I have found that this generates a total of 11440 combinations if or just about a factor 1000 fewer numbers to check.
As you have noticed I have a method for checking the number once I generate a new combination. This method calculates if we found a sequence that hits 89 and in that case how many permutations there are in it.

private int CheckNumber(int[] number) {

//make the array into a number
int factor = 1;
int candidate = 0;
for (int i = number.Length - 1; i >= 0; i--) {
candidate += factor * number[i];
factor *= 10;
}

//Calc sequence
while (candidate != 89 && candidate != 1) {
candidate = nextNumber(candidate);
}

if (candidate == 89) {
//calc the number of each digit
int[] numDigits = new int;
for (int i = 0; i < number.Length; i++) {
numDigits[number[i]]++;
}

//calc the multinomial coef
int result = Factor(number.Length);
for (int i = 0; i < numDigits.Length; i++) {
result /= Factor(numDigits[i]);
}
return result;
}

return 0;
}

In this we reuse the NextNumber function we wrote earlier.

So with a factor 1000 fewer numbers to check I would expect about a factor 1000 reduction in execution time, in fact we gain a little less with the result clocking in at

There are 8581146 numbers that ends in 89
Solution took 4,8619 ms

This is much more satisfying runtime I think.

Wrapping up

With a rather long post for going through to different solutions. We have now gotten another problem under the belt with what I consider a satisfying result of less than 5ms. You can find the source code for both solutions here.

Since there are many people who have solved this, my guess is that there are some of you that approached this differently. I would love to hear about that approach.

The credit for the image for this post goes to Marie-ll who shared it under the creative commons license. Posted by Kristian SuprDewd

Using Horner’s rule, we can change:

int factor = 1;
int candidate = 0;
for (int i = number.Length - 1; i >= 0; i--) {
candidate += factor * number[i];
factor *= 10;
}

into:

int candidate = 0;
for (int i = 0; i < number.Length; i++) {
candidate = candidate * 10 + number[i];
}

Doesn’t affect the solution much, but it’s way neater 🙂 Kristian

Hi Suprdewd

You are absolutely right, it is a nice solution and easier to read.

/Kristian Pubudu

Hi,

I’m a bit confused about this one. It says every starting number ends in either 1 or 89. But I just noticed that some numbers have repeating numbers other than 1 or 89(my brute force code didn’t give out the expected output. so i was printing some lists to see). for example, 289 and 298.. the chain goes like -> 289 -> 149, 98, 145, 42, 20, 4, 16, 37, 58, 89, 145

clearly, in the above sequence, 145 is the number which starts to repeat first. not 89! Kristian

I don’t think the problem states that the you can’t enter the cycle elsewhere, just that eventually all number reach 1 or 89. Pubudu

Ohh i see… i thought they meant that all starting numbers start to repeat from either 1 or 89.. my code gives the expected output, when i check for 1 and subtract that number from 9999999. but when i directly check for 89, it gives out 4 million something. apparently, the case is the one i mentioned above, with the code not counting the ones which starts to repeat from a number other than 89… I used the following approach. Created a list of all endings up to 568. Then ran through all the 10 million numbers and based on the first iteration was able to decide whether it would end in 89 or 1

<?php
\$f=[];
for(\$x=1;\$x<568;\$x++){
\$s=\$x;
while(\$s!=1 && \$s!=89){
\$c=0;
\$n=str_split(\$s);
foreach(\$n as \$b)
\$c+=pow(\$b,2);
\$s=\$c;
};
if(\$s==89)
array_push(\$f,\$x);
}

\$tot=0;
for(\$x=1;\$x<10000000;\$x++){
\$c=0;
foreach(str_split(\$x) as \$b)
\$c+=pow(\$b,2);
if(in_array(\$c,\$f))
\$tot++;
}
echo \$tot;
?> Jean-Marie Hachey

Some results from algo (1) …

(8 581 146 x 100)/10 000 000 = 85.81 %

(856 929 x 100)/1 000 000= 85.69%

(85 623 x 100)/100 000= 85.623%

(8 558 x 100)/10 000= 85.58%

(857 x 100)/1 000= 85.7%

For the intervals calculated above, we can see that there are about 85% of unhappy numbers and about 15% of happy numbers.

___

Sources:

1) Project Euler 92
Kristian’s algorithm
http://www.mathblog.dk/files/euler/Problem92.cs
2) Happy numbers
http://en.wikipedia.org/wiki/Happy_number
3) Microsoft Visual C# 2010 Express
4) Microsoft Office Excel (2007)

[…] added we improvement learned from Kristian’s excellent Math Blog is to take similar “digited” numbers and simply add the multinominal coefficient to […]

[…] For a faster solution which uses the observation that the sum of squared digits is invariant under permutation to reduce the number of computations, see MathBlog. […] Michael Yuan

Hey Kristian I love your blog and it gives me lots of insight on writing algorithms. For this problem, I found the fastest approach is to use dynamic programming and loop through from 1 to 10 million, storing whether the number converges to 89 or 1. The below algorithm runs on my vm in around 415ms

package eulerproblems;

public class P092 {

public static void main(String[] args) {
long init = System.nanoTime();
int[] numbers = new int;
numbers = 1;
numbers = 89;
for (int i = 1; i &lt;= 10000000; i++) {
if (numbers[i] == 0) {
int curr = i;
int convergence = 0;
while (true) {
int digitSum = 0;
while (curr &gt; 0) {
int digit = curr % 10;
digitSum += digit * digit;
curr /= 10;
}
if (numbers[digitSum] != 0) {
convergence = numbers[digitSum];
break;
} else {
curr = digitSum;
}
}
for (int j = 0; j &lt; numbersSquare.size(); j++) {
}
numbers[i] = convergence;
}
}
// could have did something inside the big for loop to count, too lazy to change
int total = 0;
for (int i = 0; i &lt;= 10000000; i++) {
if (numbers[i] == 89)
total++;
}
System.out.println(total);
System.out.println((System.nanoTime() - init) / 1000000 + &quot;ms&quot;);
}
} Michael Yuan

hmm looks like you had a similar approach in the brute force algorithm, maybe mine is faster because I did this 2 years later than you, ahaha Basim

I also did a brute-force approach in Java but using a recursive strategy. It runs in only 610ms:

public project92() {
long before = System.currentTimeMillis();

int count = 0;

for(int i = 2; i 0){
ret += (n % 10)*(n % 10);

n /= 10;
}

return ret;
}

public static void main(String[] args) {
new project92();
}