Problem

Many numbers can be expressed as the sum of a square and a cube. Some of them in more than one way.

Consider the palindromic numbers that can be expressed as the sum of a square and a cube, both greater than 1, in exactly 4 different ways. For example, 5229225 is a palindromic number and it can be expressed in exactly 4 different ways:

  • 22852 + 203
  • 22232 + 663
  • 18102 + 1253
  • 11972 + 1563

Find the sum of the five smallest such palindromic numbers.

Analysis

The given palindrome number is 7 digit. Hence, we start iterating with all palindromes that are atleast 7 digits in length and go up to the point where we find the first 5 palindromes satisfying the given condition. Finding palindromes iterating over a sequence is time consuming, hence, create a small function that generates only palindromes.

For a palindrome of digit length n, when n is even, a simple loop of n/2 digits can be run. Thus for palindromes of length 4, a loop from 10 to 99 can be run, where the number and its reverse are appended. Similarly for a palindrome of digit length n, when n is odd, a first loop for (n - 1)/2 digits and a second loop from 0 to 9 can be run. Thus for palindromes with a length 5, run an outerloop from 10 to 99 and an inner loop from 0 to 9. Concatenate the number, the middle element and the reverse of the number to generate the palindromes.

To check for the given condition that the number be expressed as a sum of square and cube, where both numbers are greater than 2. Simply run a loop from 2 to cube root of number minus 4 (for the square will be of atleast 2). Then see if the square root is perfect or not. Keep counting valid combinations. If a number has 4 such combinations consider it for the solution.

Solution

Code part of Project Maer on Github. Runs under 2 seconds in Java 6.

package com.sangupta.maer.page7;
 
import com.sangupta.maer.util.MathUtil;
 
/**
 * Problem 348 on Project Euler, http://projecteuler.net/index.php?section=problems&id=348
 *
 * @author <a href="http://www.sangupta.com">Sandeep Gupta</a>
 * @since 06-Sep-2011
 */
public class Problem348 {
     
    private static int found = 0;
     
    private static long sum = 0;
 
    /**
     * @param args
     */
    public static void main(String[] args) {
        iterateOnPalindromes(7, 12);
        System.out.println("Sum: " + sum);
    }
     
    private static void iterateOnPalindromes(final int startDigits, final int maxDigits) {
        for(int numDigits = startDigits; numDigits <= maxDigits; numDigits++) {
            if(MathUtil.isEven(numDigits)) {
                long end = (long) Math.pow(10, (numDigits / 2));
                long start = end / 10;
                 
                // loop
                for(long i = start; i < end; i++) {
                    String palindrome = String.valueOf(i);
                    palindrome = palindrome + new StringBuilder(palindrome).reverse().toString();
                    boolean stopLoop = checkPalindrome(palindrome);
                    if(stopLoop) {
                        return;
                    }
                }
            } else {
                // this is odd digit based
                int digitGroupLength = numDigits - 1;
                long end = (long) Math.pow(10, (digitGroupLength / 2));
                long start = end / 10;
                 
                // loop
                for(long i = start; i < end; i++) {
                    // the middle digit comes from the second loop
                    for(int middle = 0; middle < 10; middle++) {
                        String palindrome = String.valueOf(i);
                        palindrome = palindrome + String.valueOf(middle) + new StringBuilder(palindrome).reverse().toString();
                        boolean stopLoop = checkPalindrome(palindrome);
                        if(stopLoop) {
                            return;
                        }
                    }
                }               
            }
        }
    }
 
    /**
     * @param palindrome
     * @return
     */
    private static boolean checkPalindrome(String palindrome) {
        Long number = Long.parseLong(palindrome);
        if(isPalindromeRepresentable(number)) {
            System.out.println("Found " + number);
            found++;
            sum += number;
        }
         
        if(found == 5) {
            return true;
        }
        return false;
    }
 
    private static boolean isPalindromeRepresentable(final long number) {
        int cubeLimit = (int) Math.cbrt(number - 4);
         
        int countForms = 0;
         
        for(int testNumber = 2; testNumber <= cubeLimit; testNumber++) {
            int cube = testNumber * testNumber * testNumber;
            long diff = number - cube;
            double squareRoot = Math.sqrt(diff);
            int intSquareRoot = (int) squareRoot;
            if(squareRoot == intSquareRoot) {
                countForms++;
            }
        }
         
        if(countForms == 4) {
            return true;
        }
         
        return false;
    }
}