p044.py

# -*- coding: utf-8 -*-
"""
Created on Thu Jul  2 09:00:49 2020

@author: zhixia liu
"""

"""
Project Euler 44: Pentagon numbers
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?
"""

#%% naive
from tqdm import tqdm
from math import sqrt

def  isPentagonal(m):
    t = (1+sqrt(1+24*m))/6
    return t.is_integer()

pentagonal_lst = [n*(3*n-1)/2 for n in range(1,10000)]

results = []
for m in tqdm(range(1,5000)):
    for i in range(5000-m):
        a=pentagonal_lst[i+m]
        b=pentagonal_lst[i]
        if isPentagonal(a-b) and isPentagonal(a+b):
            results.append((a,b))
            break

print(results)
print(min(results,key=lambda x: x[0]-x[1]))

#%% others
import sys
def NaturalNumbers():
    n=1
    while True:
        yield n
        n += 1
def P(n): # pentagonal
    return (3*n*n-n)/2
def isdoubleP( x): # where `x' is P(m)+P(k) or P(m)-P(k)
    q, r = divmod( x, 2)
    return r == 0 and isPentagonal(q)
# main
for m in NaturalNumbers():
    Pm = P(m)
    for Pk in map(P, range(1, m+1)): 
        if isdoubleP( Pm - Pk) and isdoubleP( Pm + Pk):
            print(Pk)
            sys.exit(0)# 18 seconds