Satanoscillatemymetallicsonatas

by Gilbert Keith

The post has nothing to do with heavy metal.

You will notice that the title is palindromic – today’s Project Euler question also deals with palindromes.

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 was agonizing over how to start this one, but realized that it would be easier to first compute the numbers which fit the category, and then check for palindromicness. Since the criteria are very clear, you easily verify whether a number fits or not.

You’ve seen the isPalindrome function before, so nothing new there.

Solution: runs in about 180ms.

import java.util.ArrayList;


public class Problem125 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		long begin = System.currentTimeMillis();
		//capture the total sum of the numbers.
		long totalSum = 0L;
		//the maximum value for a number that fits.
		long maxInt = 100000000L;
		//cache each found number so that it doesn't get
		//counted twice in totalSum;
		
		ArrayList<Long> listOfNums = new ArrayList<Long>();
		
		//since we are working with squares and
		//we know the absolute upper bounds
		//start working backwards from 9999 towards 1.
		for (long l=9999L; l > 0; l--) {
			//calculate the sum so that we can 
			//break out if it exceeds maxInt;
			long sum = 0L;
			//cache the number which contributes
			long squareNum =0L;
			for (long k = l; k > 0; k--) {
				//square k;
				squareNum = k*k;
				sum+=squareNum;
				// if k = l, then this isn't yet a "sum"
				if (k==l) continue;
				// if the sum exceeds the limit, break;
				if (sum > maxInt) break;
				//if the sum isn't palindromic, keep trying
				if (!isPalindromic(sum)) continue;
				//if we've already found the sum, keep going.
				if (listOfNums.contains(sum)) continue;
				//the sum must have satisfied all the criteria
				//so add it to the total sum and cache it.
				totalSum += sum;
				listOfNums.add(sum);
			}
			
		}
		
		System.out.println("Answer: " + totalSum);
		long end = System.currentTimeMillis();
		System.out.println("Time: " + (end-begin) + " ms");
	}
	
	public static boolean isPalindromic(long number) {
		boolean yesOrNo = false;
		String numString = "" + number; //convert input to string.
		StringBuffer reverseString =  new StringBuffer(numString);
		reverseString=reverseString.reverse();
		if (reverseString.toString().equals(numString)) yesOrNo = true; //if reverseString is equal to numString, then the number is palindromic.
		return yesOrNo;
	}


}

Advertisements