Problem 44: Pentagon Numbers

Project Euler Problem 44 Solution

EulerSolve provides an optimized solution for Project Euler Problem 44, Pentagon Numbers, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary The $n$-th pentagonal number is $$P_n=\frac{n(3n-1)}{2}.$$ We seek indices $j<k$ such that both $P_j+P_k$ and $P_k-P_j$ are pentagonal, and we want the positive difference $$D=P_k-P_j$$ to be as small as possible. A naive search over all pairs is infinite, so the real task is to exploit the arithmetic structure of pentagonal numbers and organize the search so that most candidates are rejected quickly. Mathematical Approach The implementations are built around three ingredients: the explicit formula for pentagonal numbers, a constant-time test for deciding whether a number is pentagonal, and a monotone scan order that allows safe pruning inside the nested loops. The pentagonal sequence is strictly increasing The first few pentagonal numbers are $$1,\ 5,\ 12,\ 22,\ 35,\ 51,\ 70,\ 92,\dots$$ and their growth is quadratic. More importantly for the code, the sequence is strictly increasing because $$P_{n+1}-P_n=\frac{(n+1)(3n+2)-n(3n-1)}{2}=3n+1>0.$$ This monotonicity is the key invariant used by the search. For a fixed larger index $k$, if we inspect smaller indices in the order $j=k-1,k-2,\dots,1$, then $P_j$ decreases and therefore the difference $P_k-P_j$ increases step by step. Testing whether an integer is pentagonal Suppose $x=P_n$....

Detailed mathematical approach

Problem Summary

The $n$-th pentagonal number is

$$P_n=\frac{n(3n-1)}{2}.$$

We seek indices $j<k$ such that both $P_j+P_k$ and $P_k-P_j$ are pentagonal, and we want the positive difference

$$D=P_k-P_j$$

to be as small as possible. A naive search over all pairs is infinite, so the real task is to exploit the arithmetic structure of pentagonal numbers and organize the search so that most candidates are rejected quickly.

Mathematical Approach

The implementations are built around three ingredients: the explicit formula for pentagonal numbers, a constant-time test for deciding whether a number is pentagonal, and a monotone scan order that allows safe pruning inside the nested loops.

The pentagonal sequence is strictly increasing

The first few pentagonal numbers are

$$1,\ 5,\ 12,\ 22,\ 35,\ 51,\ 70,\ 92,\dots$$

and their growth is quadratic. More importantly for the code, the sequence is strictly increasing because

$$P_{n+1}-P_n=\frac{(n+1)(3n+2)-n(3n-1)}{2}=3n+1>0.$$

This monotonicity is the key invariant used by the search. For a fixed larger index $k$, if we inspect smaller indices in the order $j=k-1,k-2,\dots,1$, then $P_j$ decreases and therefore the difference $P_k-P_j$ increases step by step.

Testing whether an integer is pentagonal

Suppose $x=P_n$. Starting from $x=n(3n-1)/2$, multiply by 24 and complete the square:

$$24x+1=12n(3n-1)+1=(6n-1)^2.$$

So an integer $x>0$ is pentagonal exactly when $24x+1$ is a perfect square and

$$n=\frac{1+\sqrt{24x+1}}{6}$$

is an integer. Equivalently, if $s=\sqrt{24x+1}$, then $s$ must be integral and $s\equiv 5 \pmod 6$. The implementations use this inverse test instead of scanning a list for membership. That makes every sum and difference check an $O(1)$ arithmetic operation.

Rewriting the difference condition

For $j<k$, the difference between two pentagonal numbers can be written as

$$P_k-P_j=\frac{k(3k-1)-j(3j-1)}{2}=\frac{(k-j)\bigl(3(k+j)-1\bigr)}{2}.$$

This formula shows immediately that the gap depends on both the index difference $k-j$ and the index sum $k+j$. It is useful conceptually, but the code relies on an even simpler fact: for fixed $k$, once $j$ moves downward, the quantity $P_k-P_j$ can only get larger. Therefore, if a valid pair has already produced a best difference $D_{\min}$ and the current candidate satisfies

$$P_k-P_j\ge D_{\min},$$

then every later candidate in that same inner loop is automatically worse. The loop can stop immediately without missing a better answer.

The sum condition has no comparable monotone shortcut, so each remaining candidate still needs a direct pentagonal test on

$$P_k+P_j.$$

Worked example

Take $P_4=22$ and $P_7=70$. Their sum is

$$22+70=92,$$

and

$$24\cdot 92+1=2209=47^2,$$

so $92$ is pentagonal, in fact $92=P_8$. But their difference is

$$70-22=48,$$

and

$$24\cdot 48+1=1153,$$

which is not a perfect square. So this pair satisfies the sum condition but fails the difference condition. The example shows why both tests are essential: a rare pentagonal sum does not imply a pentagonal difference.

How the Code Works

The C++, Python, and Java implementations first precompute the pentagonal numbers $P_1,P_2,\dots,P_M$ for a configurable upper index bound $M$; in the provided programs the default is 5000. Keeping these values in an array avoids recomputing the quadratic formula during the pair scan.

To decide whether a sum or difference is pentagonal, the implementation applies the inverse criterion $24x+1=(6n-1)^2$. One version uses an integer square root to check the discriminant exactly; the other two compute a square root, round to the nearest candidate index, and then substitute that index back into $n(3n-1)/2$. In all three cases, the final acceptance step is exact because the recovered index must reproduce the original value. Before the full search begins, the programs also verify this predicate on small known cases such as 12 and 35, reject 36, and confirm the larger pentagonal number 40755.

The main search enumerates the larger index increasingly. For each larger index, it walks the smaller index downward, computes the current difference and sum, and uses the monotonicity of the difference to stop the inner loop as soon as the current gap is no longer better than the best valid one already found. Only the candidates that survive this pruning are tested for the two pentagonal conditions. Whenever both tests succeed, the best difference is updated. After all indices up to the chosen bound have been processed, that smallest recorded difference is returned.

Complexity Analysis

If $M$ is the search bound on the larger index, precomputing the pentagonal table costs $O(M)$ time and $O(M)$ space. The nested scan over pairs costs $O(M^2)$ time in the worst case, because it may inspect on the order of $M(M-1)/2$ pairs. Each inspection performs only constant-time arithmetic together with two constant-time pentagonality checks.

The pruning rule often saves a noticeable fraction of the inner loop once a good candidate has been found, but it does not change the worst-case asymptotic bound. So the method is still a quadratic search in theory, yet it is practical here because the bound is modest and the direct pentagonal test is very cheap.

Footnotes and References

Problem page: Project Euler 44
Pentagonal numbers: Wikipedia - Pentagonal number
Further formulas: MathWorld - Pentagonal Number
Sequence data: OEIS A000326

Problem 44 source code

C++

#include <cmath>
#include <cstdint>
#include <iostream>
#include <limits>
#include <string>
#include <vector>

namespace {

using i64 = std::int64_t;

struct Options {
    int max_index = 5000;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);

        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--max-index=", options.max_index)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }

    return options.max_index >= 10;
}

i64 pentagonal(const i64 n) {
    return n * (3 * n - 1) / 2;
}

bool is_pentagonal(const i64 x) {
    if (x <= 0) {
        return false;
    }
    const long double disc = 1.0L + 24.0L * static_cast<long double>(x);
    const long double root = std::sqrt(disc);
    const long double n = (1.0L + root) / 6.0L;
    const i64 k = static_cast<i64>(std::llround(n));
    return pentagonal(k) == x;
}

i64 solve(const int max_index) {
    std::vector<i64> p(static_cast<std::size_t>(max_index + 1));
    for (int i = 1; i <= max_index; ++i) {
        p[static_cast<std::size_t>(i)] = pentagonal(i);
    }

    i64 best = std::numeric_limits<i64>::max();

    for (int j = 2; j <= max_index; ++j) {
        for (int k = j - 1; k >= 1; --k) {
            const i64 diff = p[static_cast<std::size_t>(j)] - p[static_cast<std::size_t>(k)];
            if (diff >= best) {
                break;
            }
            const i64 sum = p[static_cast<std::size_t>(j)] + p[static_cast<std::size_t>(k)];
            if (is_pentagonal(diff) && is_pentagonal(sum)) {
                best = diff;
            }
        }
    }

    return best;
}

bool run_checkpoints() {
    if (!is_pentagonal(12) || !is_pentagonal(35) || is_pentagonal(36)) {
        std::cerr << "Checkpoint failed for pentagonal predicate" << '\n';
        return false;
    }
    if (!is_pentagonal(40755)) {
        std::cerr << "Checkpoint failed for known pentagonal value" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << solve(options.max_index) << '\n';
    return 0;
}

Python

import math
import sys

def pentagonal(n):
    return n * (3 * n - 1) // 2

def is_pentagonal(x):
    if x <= 0:
        return False
    disc = 1.0 + 24.0 * x
    root = math.isqrt(int(disc))
    # Check if disc is a perfect square
    if root * root != int(disc):
        return False
    # Calculate n = (1 + sqrt(1 + 24*x)) / 6
    n_val = (1 + root) / 6.0
    k = round(n_val)
    return pentagonal(k) == x

def solve(max_index):
    p = [0] * (max_index + 1)
    for i in range(1, max_index + 1):
        p[i] = pentagonal(i)
    
    best = float('inf')
    
    for j in range(2, max_index + 1):
        for k in range(j - 1, 0, -1):
            diff = p[j] - p[k]
            if diff >= best:
                break
            total_sum = p[j] + p[k]
            if is_pentagonal(diff) and is_pentagonal(total_sum):
                best = diff
    
    return best

def run_checkpoints():
    if not is_pentagonal(12) or not is_pentagonal(35) or is_pentagonal(36):
        return False
    if not is_pentagonal(40755):
        return False
    return True

def parse_arguments(args):
    max_index = 5000
    run_checkpoints_flag = True
    
    i = 1
    while i < len(args):
        arg = args[i]
        
        if arg == "--skip-checkpoints":
            run_checkpoints_flag = False
            i += 1
            continue
        
        if arg.startswith("--max-index="):
            try:
                max_index = int(arg[12:])
                if max_index < 10:
                    return None, None
            except ValueError:
                return None, None
        else:
            print(f"Unknown argument: {arg}", file=sys.stderr)
            return None, None
        
        i += 1
    
    return max_index, run_checkpoints_flag

def main():
    args = sys.argv[1:]
    
    max_index, run_checkpoints_flag = parse_arguments(args)
    if max_index is None:
        sys.exit(1)
    
    if run_checkpoints_flag and not run_checkpoints():
        sys.exit(2)
    
    result = solve(max_index)
    print(result)

if __name__ == "__main__":
    main()

Java

class Euler44 {

    private static class Options {
        int maxIndex = 5000;
        boolean runCheckpoints = true;
    }

    private static long pentagonal(long n) {
        return n * (3 * n - 1) / 2;
    }

    private static boolean isPentagonal(long x) {
        if (x <= 0) {
            return false;
        }
        double disc = 1.0 + 24.0 * x;
        double root = Math.sqrt(disc);
        double n = (1.0 + root) / 6.0;
        long k = Math.round(n);
        return pentagonal(k) == x;
    }

    private static long solve(int maxIndex) {
        long[] p = new long[maxIndex + 1];
        for (int i = 1; i <= maxIndex; ++i) {
            p[i] = pentagonal(i);
        }

        long best = Long.MAX_VALUE;

        for (int j = 2; j <= maxIndex; ++j) {
            for (int k = j - 1; k >= 1; --k) {
                long diff = p[j] - p[k];
                if (diff >= best) {
                    break;
                }
                long sum = p[j] + p[k];
                if (isPentagonal(diff) && isPentagonal(sum)) {
                    best = diff;
                }
            }
        }

        return best;
    }

    private static boolean runCheckpoints() {
        if (!isPentagonal(12) || !isPentagonal(35) || isPentagonal(36)) {
            System.err.println("Checkpoint failed for pentagonal predicate");
            return false;
        }
        if (!isPentagonal(40755)) {
            System.err.println("Checkpoint failed for known pentagonal value");
            return false;
        }
        return true;
    }

    private static boolean parseIntAfterPrefix(String arg, String prefix, Options options) {
        if (!arg.startsWith(prefix)) {
            return false;
        }
        String tail = arg.substring(prefix.length());
        if (tail.isEmpty()) {
            return false;
        }

        int parsed = 0;
        for (int i = 0; i < tail.length(); ++i) {
            char c = tail.charAt(i);
            if (c < '0' || c > '9') {
                return false;
            }
            parsed = parsed * 10 + (c - '0');
        }
        if (prefix.equals("--max-index=")) {
            options.maxIndex = parsed;
        }
        return true;
    }

    private static boolean parseArguments(String[] args, Options options) {
        for (String arg : args) {
            if (arg.equals("--skip-checkpoints")) {
                options.runCheckpoints = false;
                continue;
            }
            if (parseIntAfterPrefix(arg, "--max-index=", options)) {
                continue;
            }

            System.err.println("Unknown argument: " + arg);
            return false;
        }

        return options.maxIndex >= 10;
    }

    public static void main(String[] args) {
        Options options = new Options();
        if (!parseArguments(args, options)) {
            System.exit(1);
        }
        if (options.runCheckpoints && !runCheckpoints()) {
            System.exit(2);
        }

        System.out.println(solve(options.maxIndex));
    }
}