Problem #125 says

The palindromic number 595 is interesting because it can be written as the sum of consecutive squares: \(6^2 + 7^2 + 8^2 + 9^2 + 10^2 + 11^2 + 12^2\).

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 = 0^2 + 1^2\) has not been included as this problem is concerned with the squares of positive integers.

Find the sum of all the numbers less than \(10^8\) that are both palindromic and can be written as the sum of consecutive squares.

So the first thing we need to notice is that numbers like \(121 = 11^2\) don’t count for this problem because the number must be created from two or more squares. Next we need a formula for generating sums of squares and we can do some math and end up with \(\frac{(n(1+n)((2n)+1))}{6}\) and with mathematical induction we can show that this works for all natural numbers. But that formula starts at 1 and goes to n squaring each term; what about numbers like \(6^2 + 7^2 + 8^2 + 9^2 + 10^2 + 11^2 + 12^2\)? Well, if we generate all of the sums from 1 to n, we can subtract smaller sums to get the terms that don’t start at 1. Doing this for summation with all of the summations smaller than the first gives us the missing terms. From then we just need to check for palindromes and add the filtered terms.

To accomplish this we create a helper class that keeps track of the sum and where the sum starts and stops. For example let \(P(x,y) := x^2 + (x+1)^2 + … + y^2\) with \(x < y\) and \(x \neq y\). Then \(P(1,4) = 1^2 + 2^2 + 3^2 + 4^2 = 30\) and \(P(1,8) = 1^2 + 2^2 + 3^2 + 4^2 + 5^2 + 6^2 + 7^2 + 8^2 = 204\) and from this we can make \(P(5,8) = P(1,8) – P(1,4) =174\) just wash, rinse and repeat to find all of the valid sums. To make sure a sum is valid we need its starting point minus its ending point to be at least 2. We take these and check for the palindrome property and from there it’s an addition problem.

Solution provided in C#/mono and runs in 5 seconds or so with most of the time being spent checking to make sure we’re not adding duplicates. This program could potentially be made much faster if we were to make the math slightly more complicated to avoid creating all of these summation helper objects. But its fast enough for this problem.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace Problem125
{
    class Program
    {
        static void Main(string[] args)
        {
            Stopwatch sw = new Stopwatch();
            sw.Start();
            List<SumHolder> Possibles = new List<SumHolder>();
            long max = 100000000000L;//100000000L;
			
			long t = 1L;
			while (SumOfCSquares(t-1L) <=max)
			{
				SumHolder s = new SumHolder(SumOfCSquares(t),t,1L);
				Possibles.Add(s);
				t++ ;
			}
			List<SumHolder> Generated = new List<SumHolder>();
			foreach (SumHolder s in Possibles)
			{
				foreach (SumHolder s2 in Possibles)
				{
					if (s.Sum > s2.Sum)
					{
						if (s.Sum != s2.Sum)
						{
							SumHolder temp = new SumHolder(s.Sum -s2.Sum, s.UpperLimit,s2.UpperLimit);
							Generated.Add(temp);
						}
					}
				}
			}
			long sum = 0L;
			int count = 0;
            
                        HashSet<long> Duplicates = new HashSet<long>();
			foreach (SumHolder s in Possibles)
			{
				if (Duplicates.Contains(s.Sum))
				    continue;
				if (s.UpperLimit - s.LowerLimit >= 1)
				{
					if (s.Sum <= 100000000L)
					{
						if (Palindrome(s.Sum))
						{
							sum += s.Sum;
							Console.WriteLine("Found :: "+s.Sum.ToString());
							Duplicates.Add(s.Sum);
							count++;
						}
					}
				}
			}
			foreach (SumHolder s in Generated)
			{
				if (Duplicates.Contains(s.Sum))
				    continue;
				if (s.UpperLimit - s.LowerLimit >= 2)
				{
					if (s.Sum <= 100000000L)
					{
						if (Palindrome(s.Sum))
						{
							sum += s.Sum;
							Console.WriteLine("Found :: "+s.Sum.ToString());
							Duplicates.Add(s.Sum);
							count++;
						}
					}
				}
			}
            sw.Stop();
            Console.WriteLine(sum);
			Console.WriteLine(count);
            Console.WriteLine(sw.Elapsed);
            Console.ReadLine();

        }
        static bool Palindrome(long n)
        {
            string s = n.ToString();
            string rs = Reverse(n.ToString());
            return rs == s;
        }
        static string Reverse(string str)
        {
            char[] array = str.ToCharArray();
            Array.Reverse(array);
            return new string(array);
        }
        static long SumOfCSquares(long n)
        {

            return (n*(1+n)*(1+(2*n)))/6L;

        }

    }
	class SumHolder
	{
		public long Sum { get; set; }
		public long UpperLimit { get; set; }
		public long LowerLimit { get; set; }
		public SumHolder(long s, long u, long l)
		{
			this.Sum = s;
			this.UpperLimit = u;
			this.LowerLimit = l;
		}
	}
	
}