Project Euler: Problem 45 – Triangular, pentagonal, and hexagonal

Problem 45:

Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:

Triangle Tn=n(n+1)/2 1, 3, 6, 10, 15, …
Pentagonal Pn=n(3n-1)/2 1, 5, 12, 22, 35, …
Hexagonal Hn=n(2n-1) 1, 6, 15, 28, 45, …

It can be verified that T285 = P165 = H143 = 40755.
 
Find the next triangle number that is also pentagonal and hexagonal.

Idea:

Looking at the list of triangle and hexagonal numbers, I made an educated guess that all hexagonal numbers are triangle numbers, so that narrowed down the problem to “Find the next pentagonal number that is also hexagonal”.
 
From there I just generated the next hexagonal number (since it grows faster than pentagonal numbers), and started generating pentagonal numbers until they were no longer smaller than the hexagonal number. If it just so happened that the pentagonal number was equal to the hexagonal number, I found my answer.

String answer = "";

BigInteger pent = new BigInteger("40755");
BigInteger hex = new BigInteger("40755");
int h = 143;
int p = 165;
boolean matches = false;

while(!matches) {
   h++;
   hex = BigInteger.valueOf(h).multiply(
            BigInteger.valueOf(2).multiply(
               BigInteger.valueOf(h)).subtract(BigInteger.ONE));
   while(pent.compareTo(hex) < 0) {
      p++;
      pent = BigInteger.valueOf(p).multiply(
               BigInteger.valueOf(3).multiply(
                  BigInteger.valueOf(p)).subtract(BigInteger.ONE))
                   .divide(BigInteger.valueOf(2));
   }
   if(pent.compareTo(hex) == 0) {
      matches = true;
   }
}

answer = hex.toString();

Project Euler: Problem 44 – Pentagon numbers

Problem 44:

Pentagonal numbers are generated by the formula, Pn=n(3n-1)/2. The first ten pentagonal numbers are:
 
1, 5, 12, 22, 35, 51, 70, 92, 117, 145, …
 
It can be seen that P4 + P7 = 22 + 70 = 92 = P8. However, their difference, 70 – 22 = 48, is not pentagonal.
 
Find the pair of pentagonal numbers, Pj and Pk, for which their sum and difference is pentagonal and D = |Pk – Pj| is minimized; what is the value of D?

Idea:

First I generated a large list of pentagonal numbers (not knowing how many I would need). I used two lists, one regular so I could access the numbers by index (i.e. 5th pentagonal number + 7th pentagonal number), and one hashed so I could quickly find out if the resulting sum and difference were pentagonal numbers (I initially tried it without, and found that seeing if the regular list contained a number was taking up a significant amount of time).
 
If the difference was smaller than anything I’ve encountered so far, save it.

int answer = Integer.MAX_VALUE;

List<Integer> nums = EulerUtils.pentagonalNumbers(5000);
HashSet<Integer> numbers = new HashSet<Integer>();
for(Integer n:nums) {
   numbers.add(n);
}
for(int j = 0; j < numbers.size()-1; j++) {
   for(int k = j+1; k < numbers.size(); k++) {
      int sum = nums.get(j) + nums.get(k);
      if(!numbers.contains(sum)) {
         continue;
      }
      int difference = nums.get(k) - nums.get(j);
      if(!numbers.contains(difference)) {
         continue;
      }
      if(difference < answer) {
         answer = difference;
      }
   }
}

Note: pentagonalNumbers() is a utility method that generates a list of pentagonal numbers.