Project Euler Solution #44: Pentagon numbers

Pentagonal numbers are generated by the formula, P_n=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 P₄ + P₇ = 22 + 70 = 92 = P₈. However, their difference, 70 − 22 = 48, is not pentagonal.

Find the pair of pentagonal numbers, P_j and P_k, for which their sum and difference are pentagonal and D = |P_k − P_j| is minimised; what is the value of D?

Solution

A pentagonal number is generated by \(P_n = \frac{1}{2}n(3n-1)\) and creates the set \(P=\{P_n | n \in\mathbb{N}\}\). We now want to find \(D\) such that \(P_j+P_k\in P, P_k-P_j\in P, D=\min |P_j-P_k|\). In order to check if a number is a pentagonal number, we calculate the inverse of \(P_n\):

\[ \begin{array}{rrl} & x =& P_n\\ & =& \frac{1}{2}n(3n-1)\\ \Leftrightarrow & 0 =& 3n^2-n-2x\\ \Leftrightarrow & n_{1,2} =& \frac{1\pm \sqrt{1+4\cdot 3\cdot 2x}}{2\cdot 3}\\ & =& \frac{1\pm \sqrt{1+24x}}{6} \end{array} \]

We can ignore the negative case since pentagonal numbers are positive. It follows that

\[x \text{ is pentagonal} \Leftrightarrow \frac{1+ \sqrt{1+24x}}{6}\in\mathbb{N} \Leftrightarrow 1+24x \text{ is perfect square} \land \sqrt{1+24x}+1\equiv 0\pmod{6}\]

This can be implemented, using the fmod capabilities of JavaScripts modulo operator, by checking for a perfect square with \(r \equiv 0 \pmod{ 1} \) and \(r+1\equiv 0\pmod{6} \Leftrightarrow r\equiv 5\pmod{6} \). Checking for the second relation implies the first decimal places check under the definition of fmod:

function isPentagonal(x) {
  var r = Math.sqrt(1 + 24 * x);
  return r % 6 === 5;
}

The next thing that could come in handy is a fast way of generating the sequence. Lets say the difference between two consecutive pentagonal numbers is \(q\):

\[\begin{array}{rrl} & P_{k+1} &= P_k + q\\ \Leftrightarrow & \frac{1}{2}(k+1)(3(k+1)-1) &= \frac{1}{2}k(3k-1)+q\\ \Leftrightarrow & 3k^2+2k+3k+2 &= 3k^2-k + 2q\\ \Leftrightarrow & q &= 3k+1 \end{array}\]

Generating a set of pentagonal numbers below \(5000^2\) (rough estimate) can then be done using:

var P = new Set;
for (var i = 1, c = 1; c < 25000000; i+= 3, c+= i) {
  P.add(c);
}

The first naive way to find \(D\) is to quadratically loop over the set and check if the sum and difference is also an element of the set:

function solution() {

  for (var Pj of P) {

    for (var Pk of P) {

      if (P.has(Pk - Pj) && P.has(Pj + Pk)) {
        console.log(Pk - Pj);
      }
    }
  }
}

This algorithm however is pretty slow. One improvement is to skip impossible numbers. We now use the isPentagonal function to check, instead of generating a large set:

function solution() {

  for (var j = 1; j < 5000; j++) {
    var Pj = j * (3 * j - 1) / 2;

    for (var k = j + 1; k < 5000; k++) {
      var Pk = k * (3 * k - 1) / 2;

      if (isPentagonal(Pk - Pj) && isPentagonal(Pj + Pk)) {
        console.log(Pk - Pj);
      }
    }
  }
}

We got the right answer already but it's not satisfying that we guess the upper bound and are still quadratic. Combining some tricks from before lets us come up with this solution:

function solution() {

  var nums = [1, 5, 12];

  for(var n = 10, Pn = 22; ; n+= 3, Pn+= n) {

    nums.push(Pn);

    for (var i = 0; i < nums.length; i++) {

      var a = Pn - nums[i];
      var b = nums[i];

      if (isPentagonal(a) && isPentagonal(Math.abs(a - b))) {
        console.log(Math.abs(a-b));
        return;
      }
    }
  }
}