[Math] Project Euler 44, solving it using Google OR-tools

Project Euler 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?

#!/usr/bin/python3

# pip install ortools
# https://pypi.org/project/ortools/
from ortools.constraint_solver import pywrapcp

def main():
  solver = pywrapcp.Solver("PE_44")

  max_limit=10**7 # may be raised gradually

  P1=solver.IntVar(0, max_limit, "P1")
  P2=solver.IntVar(0, max_limit, "P2")
  P_diff=solver.IntVar(0, max_limit, "P_diff")
  P_sum=solver.IntVar(0, max_limit, "P_sum")

  n1=solver.IntVar(0, max_limit, "n1")
  n2=solver.IntVar(0, max_limit, "n2")
  n_diff=solver.IntVar(0, max_limit, "n_diff")
  n_sum=solver.IntVar(0, max_limit, "n_sum")

  solver.Add(P1>1)
  solver.Add(P2>1)
  solver.Add(P_diff>1)
  solver.Add(P_sum>1)

  solver.Add(P1!=P2)

  solver.Add(n1>1)
  solver.Add(n2>1)
  solver.Add(n_diff>1)
  solver.Add(n_sum>1)

  solver.Add(2*P1==n1*(3*n1-1))
  solver.Add(2*P2==n2*(3*n2-1))
  solver.Add(2*P_diff==n_diff*(3*n_diff-1))
  solver.Add(2*P_sum==n_sum*(3*n_sum-1))

  solver.Add(P1-P2==P_diff)
  solver.Add(P1+P2==P_sum)

  # objective
  objective = solver.Minimize(P_diff, 1)

  solution = solver.Assignment()

  db = solver.Phase([P1, P2, P_diff, P_sum, n1, n2, n_diff, n_sum],
                    solver.CHOOSE_MIN_SIZE_LOWEST_MAX,
                    solver.ASSIGN_MIN_VALUE)

  solver.NewSearch(db, [objective])
  assert solver.NextSolution()==True
  print(P1)
  print(P2)
  print(P_diff)
  print(P_sum)
  print(n1)
  print(n2)
  print(n_diff)
  print(n_sum)
  solver.EndSearch()

main()

P1(7042750)
P2(1560090)
P_diff(5482660)
P_sum(8602840)
n1(2167)
n2(1020)
n_diff(1912)
n_sum(2395)

And again, my solution is not fast. 1-2 hours. But I spent maybe 10-15 minutes on coding, and I have no corresponding math experience.

(the post first published at 20240803.)

List of my other blog posts.

Subscribe to my news feed,

Yes, I know about these lousy Disqus ads. Please use adblocker. I would consider to subscribe to 'pro' version of Disqus if the signal/noise ratio in comments would be good enough.