Project Euler 125: Finding square sums that are palindromic

Problem 125 of Project Euler deals with a property we have worked with before, palindromic numbers. The problem reads

The palindromic number 595 is interesting because it can be written as the sum of consecutive squares: 62 + 72 + 82 + 92 + 102 + 112 + 122.

There are exactly eleven palindromes below one-thousand that can be written as consecutive square sums, and the sum of these palindromes is 4164. Note that 1 = 02 + 12 has not been included as this problem is concerned with the squares of positive integers.

Find the sum of all the numbers less than 108 that are both palindromic and can be written as the sum of consecutive squares.

I don’t think there is a way we can avoid checking a whole lot of numbers. However, we can either generate all palindromic numbers and check if them are sum of squares. Or we can go the other way and generate all sum of squares and check if they are palindromes. I took the latter approach since we already have an efficient solution for check if a number is palindromic.

All we need to solve this problem is to create two nested for loops in order to generate all the sums of squared numbers. However, there is one caveat, which is that there are a few sum of consecutive squares that give us the same number. So if we don’t keep track of the found numbers, we might find the same number several times.

So the code for solving this problem looks like

int limit = 100000000;
double sqrtLimit = Math.Sqrt(limit);

long sum = 0;
SortedSet list = new SortedSet();

for (int i = 1; i <= sqrtLimit; i++) {
    int number = i*i;
    for (int j = i + 1; j <= sqrtLimit; j++) { number += j * j; if (number > limit) break;

        if (IsPalindrome(number) && !list.Contains(number) ) {
            sum += number;
            list.Add(number);                        
        }

    }
}

I don’t think there are many comments I can come up with. It runs in 32ms on my computer. I have made several attempts to optimize the code. However, I haven’t really found anything to speed it up. Among other things  I tried pre-generating all squares, but that just took up more memory and didn’t give anything.

I get the result

sum of palindromic squares = 2906969179

You can check the code or Problem 36, to see the palindromic check.

Posted by Kristian

4 comments

Jean-Marie Hachey

Hi Kristian,

The list from OEIS shows 17 palindromic numbers between 1 and 1000 which are sum of consecutive squares.

___

A180436
Palindromic numbers which are sum of consecutive squares.

1, 4, 5, 9, 55, 77, 121, 181, 313, 434, 484, 505, 545, 595, 636, 676,
818, 1001, 1111, 1441, 1771, 4334, 6446, 10201, 12321, 14641,
17371, 17871, 19691, 21712, 40804, 41214, 42924, 44444, 44944,
46564, 51015, 65756, 69696, 81818, 94249, 97679, 99199
(list; graph; refs; listen; history; text; internal format)

http://oeis.org/search?q=palindrome+square+sum&sort=&language=english&go=Search

___

You wrote :
« Note that 1= 0^2 + 1^2 has not been included as this problem is
concerned with the squares of positive integers ».

Unexpected : 4, 9, 121, 484 and 676 in the OEIS list.

___

I agree with your statement :
« There are exactly eleven palindromes below one-thousand that can be written as consecutive square sums and the sum of these palindromes is 4164. »

Thanks for the problem.

Jean-Marie

Jean-Marie Hachey

Table 1

Palindromic numbers below 1000 as the sums of consecutive squares.

http://img849.imageshack.us/img849/5874/pe125tab1c2.jpg

Nicholas Palevsky

One speed up I tried which seem to work with this:
If you treat the sequences of consecutive squares as triangular numbers, then you only have to compute the first member of any given length (the one beginning with 1^2). Then you just do a couple of additions to get the next member of each sequence.

Carl J Appellof

I wrote out the formula for the expansion of x^2 + (x+1)^2 + … + (x+n-1)^2 (n terms)
which gave me nx^2 + (n)(n-1)x + (n-1)(n)(2n+1)/6

And since n >= 2 (must have at least two numbers to get “successive” squares, you can start with x <= sqrt((limit – 1)/2) and run n from 2 up until the formula exceeds the limit. Then decrement x and run again, until x == 1

Got the right solution, and ran in 7.8 ms on my computer.

Leave a Reply