Problem #44 hard

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, \dots$

It can be seen that $P_4 + P_7 = 22 + 70 = 92 = P_8$ . 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$ ?

Implementations

// https://projecteuler.net/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 are pentagonal and D = |Pk - Pj| is minimised; what is the value of D?

// Answer: 5482660

// Authored by: Tim Varley 💘

#include <iostream>
#include <vector>
#include <set>
#include <cmath>
#include <climits>

static bool is_pentagonal(long long n) {
    double k = (1 + sqrt(1 + 24.0 * n)) / 6;
    return k == floor(k);
}

long long pentagon_numbers() {
    std::vector<long long> pent;
    for (long long n = 1; n < 3000; n++) {
        long long p = n * (3 * n - 1) / 2;
        pent.push_back(p);
    }
    long long min_diff = LLONG_MAX;
    for (size_t i = 0; i < pent.size(); i++) {
        for (size_t j = i + 1; j < pent.size(); j++) {
            long long sum_p = pent[i] + pent[j];
            long long diff_p = pent[j] - pent[i];
            if (is_pentagonal(sum_p) && is_pentagonal(diff_p)) {
                if (diff_p < min_diff) min_diff = diff_p;
            }
        }
    }
    return min_diff;
}

#if ! defined UNITTEST_MODE
int main(int argc, char const *argv[]) {
    std::cout << pentagon_numbers() << std::endl;
}
#endif // UNITTEST_MODE

package org.tvarley.euler.solutions;

import org.tvarley.euler.Solution;
import java.util.HashSet;
import java.util.Set;

public class Solution044 implements Solution {
  public String solve() {
    Set<Long> pents = new HashSet<>();
    long minD = Long.MAX_VALUE;
    for (long k = 1; k < 3000; k++) {
      long pk = k * (3 * k - 1) / 2;
      for (long pj : pents) {
        long diff = pk - pj;
        long sum = pk + pj;
        if (pents.contains(diff) && isPentagonal(sum)) {
          if (diff < minD) minD = diff;
        }
      }
      pents.add(pk);
    }
    return Long.toString(minD);
  }

  private boolean isPentagonal(long n) {
    long k = (long) ((1 + Math.sqrt(1 + 24 * n)) / 6);
    return k * (3 * k - 1) / 2 == n;
  }
}

def solve():
    """
    Pentagon Numbers
    Pentagon 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 are pentagonal and D = |Pk - Pj| is minimised; what is the value of D?
    https://projecteuler.net/problem=44
    """
    def is_pentagonal(n):
        disc = 1 + 24 * n
        sqrt_d = int(disc ** 0.5 + 0.5)
        if sqrt_d * sqrt_d == disc:
            k = (1 + sqrt_d) // 6
            return k * (3 * k - 1) // 2 == n
        return False

    pent = []
    i = 1
    while True:
        p = i * (3 * i - 1) // 2
        pent.append(p)
        for j in range(len(pent) - 2, -1, -1):
            diff = p - pent[j]
            summ = p + pent[j]
            if is_pentagonal(diff) and is_pentagonal(summ):
                return diff
        i += 1

// Optimized implementation:
// - Uses big.Int for precise integer square root to avoid floating-point errors in isPentagonal.
// - Generates pentagonals sequentially until the pair is found, with early termination at n=10000.
// - Time: O(n^2) with fast pentagonal checks, finds answer quickly.
// - Space: O(n) for the slice of pentagonals.
package main

import "fmt"

import "math/big"

func isPentagonal(n int) bool {
  disc := big.NewInt(1 + 24*int64(n))
  sqrtD := new(big.Int).Sqrt(disc)
  sq := new(big.Int).Mul(sqrtD, sqrtD)
  if sq.Cmp(disc) != 0 {
    return false
  }
  k := new(big.Int).Add(sqrtD, big.NewInt(1))
  k.Div(k, big.NewInt(6))
  p := new(big.Int).Mul(k, big.NewInt(3))
  p.Sub(p, big.NewInt(1))
  p.Mul(p, k)
  p.Div(p, big.NewInt(2))
  return p.Cmp(big.NewInt(int64(n))) == 0
}

func main() {
  var pents []int
  for n := 1; ; n++ {
    if n > 10000 {
      fmt.Println("Pair not found within limit")
      return
    }
    p := n * (3*n - 1) / 2
    pents = append(pents, p)
    for j := 0; j < len(pents)-1; j++ {
      pj := pents[j]
      diff := p - pj
      sum := p + pj
      if isPentagonal(diff) && isPentagonal(sum) {
        fmt.Println(diff)
        return
      }
    }
  }
}

// https://projecteuler.net/problem=44
//
// Pentagon 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 are pentagonal and D = |Pk - Pj| is minimised; what is the value of D?
//
// Answer: 5482660

pub fn pentagon_numbers() -> u64 {
    let mut pentagons = Vec::new();
    let mut n = 1;
    loop {
        let p = n * (3 * n - 1) / 2;
        if p > 10_000_000 { break; } // arbitrary large limit
        pentagons.push(p);
        n += 1;
    }
    let pent_set: std::collections::HashSet<u64> = pentagons.iter().cloned().collect();

    let mut min_d = u64::MAX;
    for i in 0..pentagons.len() {
        for j in (i+1)..pentagons.len() {
            let pj = pentagons[i];
            let pk = pentagons[j];
            let sum = pj + pk;
            let diff = pk - pj;
            if pent_set.contains(&sum) && pent_set.contains(&diff) {
                if diff < min_d {
                    min_d = diff;
                }
            }
        }
    }
    min_d
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn euler_044() {
        assert_eq!(pentagon_numbers(), 5482660);
    }
}

// https://projecteuler.net/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 are pentagonal and D = |Pk - Pj| is minimised; what is the value of D?

// Answer: 5482660

// Authored by: Tim Varley 💘

#include <iostream>
#include <vector>
#include <set>
#include <cmath>
#include <climits>

static bool is_pentagonal(long long n) {
    double k = (1 + sqrt(1 + 24.0 * n)) / 6;
    return k == floor(k);
}

long long pentagon_numbers() {
    std::vector<long long> pent;
    for (long long n = 1; n < 3000; n++) {
        long long p = n * (3 * n - 1) / 2;
        pent.push_back(p);
    }
    long long min_diff = LLONG_MAX;
    for (size_t i = 0; i < pent.size(); i++) {
        for (size_t j = i + 1; j < pent.size(); j++) {
            long long sum_p = pent[i] + pent[j];
            long long diff_p = pent[j] - pent[i];
            if (is_pentagonal(sum_p) && is_pentagonal(diff_p)) {
                if (diff_p < min_diff) min_diff = diff_p;
            }
        }
    }
    return min_diff;
}

#if ! defined UNITTEST_MODE
int main(int argc, char const *argv[]) {
    std::cout << pentagon_numbers() << std::endl;
}
#endif // UNITTEST_MODE

package org.tvarley.euler.solutions;

import org.tvarley.euler.Solution;
import java.util.HashSet;
import java.util.Set;

public class Solution044 implements Solution {
  public String solve() {
    Set<Long> pents = new HashSet<>();
    long minD = Long.MAX_VALUE;
    for (long k = 1; k < 3000; k++) {
      long pk = k * (3 * k - 1) / 2;
      for (long pj : pents) {
        long diff = pk - pj;
        long sum = pk + pj;
        if (pents.contains(diff) && isPentagonal(sum)) {
          if (diff < minD) minD = diff;
        }
      }
      pents.add(pk);
    }
    return Long.toString(minD);
  }

  private boolean isPentagonal(long n) {
    long k = (long) ((1 + Math.sqrt(1 + 24 * n)) / 6);
    return k * (3 * k - 1) / 2 == n;
  }
}

const isPentagonal = (n) => {
  const k = (1 + Math.sqrt(1 + 24 * n)) / 6;
  return k === Math.floor(k);
};

module.exports = {
  answer: () => {
    const pentagonals = [];
    let i = 1;
    while (true) {
      const p = i * (3 * i - 1) / 2;
      pentagonals.push(p);
      for (let j = 0; j < pentagonals.length - 1; j++) {
        const pj = pentagonals[j];
        const pk = p;
        const sum = pj + pk;
        const diff = pk - pj;
        if (isPentagonal(sum) && isPentagonal(diff)) {
          return diff;
        }
      }
      i++;
    }
  }
};

def solve():
    """
    Pentagon Numbers
    Pentagon 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 are pentagonal and D = |Pk - Pj| is minimised; what is the value of D?
    https://projecteuler.net/problem=44
    """
    def is_pentagonal(n):
        disc = 1 + 24 * n
        sqrt_d = int(disc ** 0.5 + 0.5)
        if sqrt_d * sqrt_d == disc:
            k = (1 + sqrt_d) // 6
            return k * (3 * k - 1) // 2 == n
        return False

    pent = []
    i = 1
    while True:
        p = i * (3 * i - 1) // 2
        pent.append(p)
        for j in range(len(pent) - 2, -1, -1):
            diff = p - pent[j]
            summ = p + pent[j]
            if is_pentagonal(diff) and is_pentagonal(summ):
                return diff
        i += 1

// Optimized implementation:
// - Uses big.Int for precise integer square root to avoid floating-point errors in isPentagonal.
// - Generates pentagonals sequentially until the pair is found, with early termination at n=10000.
// - Time: O(n^2) with fast pentagonal checks, finds answer quickly.
// - Space: O(n) for the slice of pentagonals.
package main

import "fmt"

import "math/big"

func isPentagonal(n int) bool {
  disc := big.NewInt(1 + 24*int64(n))
  sqrtD := new(big.Int).Sqrt(disc)
  sq := new(big.Int).Mul(sqrtD, sqrtD)
  if sq.Cmp(disc) != 0 {
    return false
  }
  k := new(big.Int).Add(sqrtD, big.NewInt(1))
  k.Div(k, big.NewInt(6))
  p := new(big.Int).Mul(k, big.NewInt(3))
  p.Sub(p, big.NewInt(1))
  p.Mul(p, k)
  p.Div(p, big.NewInt(2))
  return p.Cmp(big.NewInt(int64(n))) == 0
}

func main() {
  var pents []int
  for n := 1; ; n++ {
    if n > 10000 {
      fmt.Println("Pair not found within limit")
      return
    }
    p := n * (3*n - 1) / 2
    pents = append(pents, p)
    for j := 0; j < len(pents)-1; j++ {
      pj := pents[j]
      diff := p - pj
      sum := p + pj
      if isPentagonal(diff) && isPentagonal(sum) {
        fmt.Println(diff)
        return
      }
    }
  }
}

// https://projecteuler.net/problem=44
//
// Pentagon 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 are pentagonal and D = |Pk - Pj| is minimised; what is the value of D?
//
// Answer: 5482660

pub fn pentagon_numbers() -> u64 {
    let mut pentagons = Vec::new();
    let mut n = 1;
    loop {
        let p = n * (3 * n - 1) / 2;
        if p > 10_000_000 { break; } // arbitrary large limit
        pentagons.push(p);
        n += 1;
    }
    let pent_set: std::collections::HashSet<u64> = pentagons.iter().cloned().collect();

    let mut min_d = u64::MAX;
    for i in 0..pentagons.len() {
        for j in (i+1)..pentagons.len() {
            let pj = pentagons[i];
            let pk = pentagons[j];
            let sum = pj + pk;
            let diff = pk - pj;
            if pent_set.contains(&sum) && pent_set.contains(&diff) {
                if diff < min_d {
                    min_d = diff;
                }
            }
        }
    }
    min_d
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn euler_044() {
        assert_eq!(pentagon_numbers(), 5482660);
    }
}

Solution Notes

Mathematical Background

Pentagonal numbers are generated by the formula $P_n = n(3n-1)/2$ . The first ten are 1, 5, 12, 22, 35, 51, 70, 92, 117, 145.

The problem requires finding pairs of pentagonal numbers where both their sum and difference are also pentagonal, and finding the pair with the minimal difference D.

Algorithm Analysis

The solution generates pentagonal numbers sequentially and checks all pairs (j,k) with j < k. For each pair, it computes sum S = Pj + Pk and difference D = Pk - Pj, then checks if both S and D are pentagonal.

Pentagonal checking uses the inverse formula: for a number x, solve $n(3n-1)/2 = x$ for integer n. This gives the quadratic $3n^2 - n - 2x = 0$ , solved as $n = (1 + \sqrt{1 + 24x})/6$ . If n is integer, x is pentagonal.

Performance Analysis

Time Complexity: O(n^2) where n ≈ 2500 (number of pentagonals up to reasonable limit), resulting in ~6 million operations
Space Complexity: O(n) for storing the list of pentagonals
Execution Time: <1 second on modern hardware
Scalability: Quadratic growth, but small n makes it practical

Key Insights

The minimal difference is 5482660 (between P_{2167} and P_{1020})
Generating pentagonals on-the-fly or precomputing doesn’t significantly affect performance
Using a set for O(1) lookup can optimize checks in some implementations
The pair is found relatively early in the sequence

Educational Value

This problem demonstrates:

Figurate number sequences and their properties
Inverse formula derivation for number checking
Quadratic equation solutions in programming
Brute force search with early termination
Mathematical optimization in computational problems