Project Euler 44

Question: 

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, ...

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 are pentagonal and D = |P_k − P_j| is minimised; what is the value of D?

문제:

오각수는 다음과 같은 방법으로 생성된다., P_n=n(3n−1)/2. 첫 열개의 오각수는 다음과 같다.

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

P₄ + P₇ = 22 + 70 = 92 = P₈ 임을 볼수 있지만, 이 두 수의 차, 70 − 22 = 48, 는 오각수가 아니다.

그 들의 합과 차가 오각수이고  D, = |P_k − P_j|, 가 가장 작은 한 쌍의 오각수, P_j and P_k,를 찾아라.   

이 때, D의 값은 얼마인가?

Solution:

from math import sqrt
import time

def isPenta(n): # 오각수 판별
    x = (sqrt(24*n+1)+1)/6
    return x == int(x)

def listPenta(n): #오각수 generator
    a = i = 1
    yield i
    while n > i:
        i += 1
        a += 3*i - 2
        yield a

start = time.time()

penta = list(listPenta(2170))
do = True
for i in range(len(penta)):
    if not do:
        break
    for j in range(i+1,len(penta)):
        if isPenta(penta[i] + penta[j]):
            if isPenta(abs(penta[i] - penta[j])):
                print("""\nD = {0}
P[{1}] = {2}, P[{3}] = {4}
Found in ...{5:.2f}s
""".format(abs(penta[i] - penta[j]),i+1,penta[i],j+1,penta[j],time.time()-start))
                do = False
                break

오각수는 다음과 같이 판별 가능하다. 출처: https://en.wikipedia.org/wiki/Pentagonal_number

처음으로 listPenta 에서 generator를 사용해봤다.

1초 걸렸다

5482660