Sums and differences of Pentagonal Numbers

by Gilbert Keith

What I did is, I think, is a little more complicated than necessary. My original intent in creating an arrayList of the pentagonal numbers was to, again, cache off all smaller the pentagonal numbers, so that when I did P_k – P_j, I’d just be able to compare the result to what’s in the arraylist. However, this didn’t pan out for some reason (the run just hangs.)

What I wanted to do:

				if (inputObj.arrOfPentNums.contains((temporaryPentNum-i)) && isNumberPentagonal((temporaryPentNum+i))) {
					yesOrNo=true;
					System.out.println("P_j: " + i + ". P_k: " + temporaryPentNum + ". P_k - P_j: " + (temporaryPentNum-i) + ". P_k + P_j: " + (temporaryPentNum + i) + ". inputObj.counter: " + inputObj.counter);
					break;
				}

Oh well. This takes about 100 ms. Not too shabby. If I wasn’t so fond of storing things in arrays and just checking some values like this guy does, then I bet it would be much faster.

I also took the time today to come up with the inverse of the generating functions for pentagonal numbers. It’d been a while since I took inverses of any kind of functions – and what I was doing made a lot of sense.

What I ended up doing:

import java.util.ArrayList;
import java.util.List;

public class Problem44 {

	/**
	 * @param args
	 */
	
	int counter=0;
	List<Integer> arrOfPentNums;
	boolean done = false;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		long begin = System.currentTimeMillis();
		Problem44 input = new Problem44();
		buildArrayOfPentNumsAndSolve(input);
		System.out.println("Time: " + (System.currentTimeMillis()-begin));
	}
	
	static void buildArrayOfPentNumsAndSolve(Problem44 inputObj) {
		inputObj.counter++;
		inputObj.arrOfPentNums = new ArrayList<Integer>();
		inputObj.arrOfPentNums.add(1);
		int tempPentNum = 1;
		
		while (!inputObj.done) {
			tempPentNum = tempPentNum + (1 + 3*inputObj.counter);
			inputObj.counter++;
			inputObj.arrOfPentNums.add(tempPentNum);
			inputObj.done = anyMatches(inputObj,tempPentNum);
		}
		
		
	}
	
	private static boolean anyMatches (Problem44 inputObj, int temporaryPentNum) {
		boolean yesOrNo = false;
			for (int i:inputObj.arrOfPentNums) {
				if (i >= temporaryPentNum) break;
				if (i < (inputObj.counter*3 + 1)) continue;
				
				if (isNumberPentagonal((temporaryPentNum-i)) && isNumberPentagonal((temporaryPentNum+i))) {
					yesOrNo=true; 
					System.out.println("P_j: " + i + ". P_k: " + temporaryPentNum + ". P_k - P_j: " + (temporaryPentNum-i) + ". P_k + P_j: " + (temporaryPentNum + i) + ". inputObj.counter: " + inputObj.counter);
					break;
				}
				if (yesOrNo) break;
			}
		return yesOrNo;
	}
	
	private static boolean isNumberPentagonal(int number) {
		double tempVal = Math.sqrt(24*number + 1);
		if ((tempVal % 1 == 0) && (tempVal % 6 == 5)) return true;
		else return false;
	}
}

Advertisements