Problem 44

Problem 44

23 May 2003

Pentagonal numbers are generated by the formula, P_n=n(3n1)/2. The first ten pentagonal numbers are:

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...

It can be seen that P₄ + P₇ = 22 + 70 = 92 = P₈. 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 is pentagonal and D = |P_k P_j| is minimised; what is the value of D?

我们令 P_j+P_k=P_m, jm只能有一种分解即不会出现P_j’+P_k’=P_m,其中P_j’!=P_j, P_k'!=P_k, 我们遍历符合条件的P_m, 将起分解后，判断是否P_k-P_j是pentagonal数    

def fun44():
    #n(3n-1)/2
    #pj+pk=pm j
    m = 3
    while 1:
        pm = m*(3*m-1)/2
        for k in range(m-1, 0, -1):
            pk = k*(3*k-1)/2
            pj = pm - pk
            if pj >= pk:
                m += 1
                break
            else:
                t = int((2*pj/3)**0.5)
                if (t+1)*(3*t+2) == 2*pj:
                    pn = pk - pj
                    t = int((2*pn/3)**0.5)
                    if (t+1)*(3*t+2) == 2*pn:
                        return pk, pj, pm, pn, pk-pj
        m += 1

answer is 5482660, pk=7042750, pj=1560090, pm=8602840, pn=5482660
time:1.68700003624