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.

Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *