Perl Weekly Challenge 147: Pentagon Numbers

Pentagonal numbers are sequence A000326 in the on-line encyclopedia of integer sequences. (Note that the OEIS has \(P (0) = 0\) as the first number).

To make life for ourselves a bit more spicy, we will try to solve this challenge without making use of multiplication or division. In order to do that, we will derive a formula for the next pentagonal number.

We define the n^th pentagonal number as:

\[ \mathcal{P} (n) = \frac{n \cdot (3 \cdot n - 1)}{2} \]

Then

\[ \begin{array}{lcl} \mathcal{P} (n + 1) & = & \frac{(n + 1) \cdot (3 \cdot (n + 1) - 1)}{2} \\ & = & \frac{(n + 1) \cdot (3 \cdot n + 2)}{2} \\ & = & \frac{3 \cdot n \cdot n + 5 \cdot n + 2}{2} \\ & = & \frac{3 \cdot n \cdot n - n + 6 \cdot n + 2}{2} \\ & = & \frac{n \cdot (3 \cdot n - 1) + 6 \cdot n + 2}{2} \\ & = & \frac{n \cdot (3 \cdot n - 1)}{2} + \frac{6 \cdot n + 2}{2} \\ & = & \mathcal{P} (n) + 3 \cdot n + 1 \\ & = & \mathcal{P} (n) + n + n + n + 1 \end{array} \]

In our solution, we will have a loop, where we process the next pentagonal, p, number in each iteration. We will also keep a hash or array of all previous pentagonal numbers.

For each previous pentagonal number s (with s <= p / 2), we will check if both p - s and p - s - s are pentagonal numbers. If so, we have the answer as s and p - s are pentagonal numbers and so are their sum (s + p - s = p) and difference (p - s - s).

We can write this in a compact way in Perl:

my %pentagon;

MAIN: for (;;) {
    state $n = 0;
    state $p = 0;
    $pentagon {$p += $n + $n + $n ++ + 1} ++;

    $_ + $_ < $p && $pentagon  {$p - $_}
                 && $pentagon  {$p - $_ - $_}
                 && say ("$_ ", $p - $_)
                 && last MAIN for keys %pentagon;
}

Find the full program on GitHub.

Most languages nowadays have hashes, maps, dictionaries or something else to store arbitrary keys and quickly find if a key is present. C does not. Therefore, in our C solution, we keep track of previous pentagonal numbers in an array. To find whether a number is present, we use a binary search. We have wrapped this into a function:

bool is_pentagonal (int candidate, int * pentagon, size_t max) {
    size_t low  = 0;
    size_t high = max;
    while (low < high) {
        size_t mid = (low + high) / 2;
        if (pentagon [mid] == candidate) {return true;}
        if (pentagon [mid]  < candidate) {low  = mid + 1;}
        if (pentagon [mid]  > candidate) {high = mid;}
    }
    return false;
}

Here, candidate is the number we're searching, pentagon is the array we are searching in, and max is the number of elements in pentagon.

The main program uses the same algorithm as Perl. It's far more verbose, because we have to do the memory management ourselves:

int main (void) {
    int *  pentagon =  NULL;
    int    n        =     0;
    int    p        =     0;
    size_t cap      =   100;
    size_t high     =     0;
    bool   done     = false;

    if ((pentagon = (int *) malloc (cap * sizeof (int))) == NULL) {
        perror ("Malloc failed");
        return (1);
    }

    while (!done) {
        p += n + n + n + 1;
        n ++;
        if (high >= cap) {
            cap *= 2;
            if ((pentagon =
                     (int *) realloc (pentagon, cap * sizeof (int))) == NULL) {
                perror ("Realloc failed");
                return (1);
            }
        }
        pentagon [high ++] = p;

        for (size_t i = 0; i < high &&
                           pentagon [i] + pentagon [i] < p &&
                          !done; i ++) {
            int seen = pentagon [i];
            if (is_pentagonal (p - seen,        pentagon, high) &&
                is_pentagonal (p - seen - seen, pentagon, high)) {
                printf ("%d %d\n", seen, p - seen);
                done = true;
            }
        }
    }

    return (0);
}

Find the full program on GitHub.