Project Euler problem 44: sums and differences of pentagonal numbers

Question

This is my code for solving the pentagonal number problem on Project Euler:

Pentagonal numbers are generated by the formula, \$P_n=n\dfrac{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, \$P_j\$ and \$P_k\$, for which their sum and difference are pentagonal and \$D = |P_k − P_j|\$ is minimized; what is the value of \$D\$?

As a beginner, I use the most basic concepts so often that sacrifices efficiency. If I could get some general tips on improving this code that would be awesome.

Key things I'd like to improve on:

How to deal with double for loops when using elements from 2 lists:

for x in a:
    for y in b:

And if there are any functions built into Python that I could use to instead of the bit of code written.

lst = []
dic = []
test = []
Final = []

for x in range(1, 3010):
    thing = int((x * (3*x - 1))/2)
    test.append(thing)
test = set(test)

for x in range(1, 3001):
    num = int((x * (3*x - 1))/2)
    lst.append(num)
lst = set(lst)

list2 = lst

for x in lst:
    for y in list2:
        num = x + y
        num2 = abs(x - y)
        dic.append({num: num2})

dic = [dict(t) for t in set([tuple(d.items()) for d in dic])]

for x in dic:
    for y in x:
        if y in test:
            Final.append(x)

for x in Final:
    for y in x:
        if x[y] in test:
            print(x)

Answer 1

Some observations:

• To do integer division in Python 3, you should use the // operator. For example, you should prefer to do (x*(3*x-1))//2 over int(x*(3*x-1)/2); the latter expression can run into annoying rounding issues for very large values of x.
• It looks like the variables test, lst, and list2 all contain the same set of numbers (in fact, lst and list2 even point to the same object). There's no reason you need different variables for all of these.
• In particular, it is completely fine to do for x in lst: followed by for y in lst:; no need to rename the second list for some reason.
• I am not sure what the point of the set comprehension [dict(t) for t in set([tuple(d.items()) for d in dic])] is; it seems like it will just return to you the original list dic, possibly permuted.
• You don't really need to store an auxiliary dictionary at all; just keep track of which valid pair of pentagonal numbers has the smallest difference. To do this, I'd recommend adding a best variable to keep track of the best valid pair so far, and moving the checks you do in your last two nested for loops into the loop where you iterate over lst.

Answer 2

Double-for

How to deal with double for loops when using elements from 2 lists:

for x in a:
    for y in b:

In a word: itertools.

If you're going to enumerate over combinatoric structures in Python, it's worth knowing. Note that you have to have a clear idea about what constitutes an equivalence. Here the double loop is inefficient: (x, y) gives the same sum and absolute difference as (y, x). Also, you don't care about repetitions: (x, x) gives difference 0, which by the terms of the question is not a pentagonal number. Taking those two things into account, you want itertools.combinations.

---

List comprehensions and iterators

for x in range(1, 3001):
    num = int((x * (3*x - 1))/2)
    lst.append(num)
lst = set(lst)

Why not just

lst = [x * (3x - 1) // 2 for x in range(1, 3001)]

? Or maybe

lst = (x * (3x - 1) // 2 for x in range(1, 3001))

? I think the latter is preferable as it works on the fly, and the expression is simple enough that recalculating it won't be too painful, but a real Pythonista may correct me.

---

Algorithm

Here I have two big questions, which may turn out to be the same question depending on the answer:

1. Where did 3010 and 3001 come from?
2. How do you know that the program gives the correct answer? You are asked to minimise \$D\$: how do you know that there isn't a larger pair of pentagonal numbers which gives a smaller \$D\$?

Answer 3

You could do:

def is_pentagonal_number(num):
    n = (0.5 + math.sqrt(0.25 - 6.0 * (-num))) / 3.0
    return n == int(n)


def project_euler_44():
    last_number_1 = 1
    n1 = 2
    best_distance = 1000 * 1000 * 1000

    while True:
        current_number_1 = n1 * (3 * n1 - 1) // 2

        if current_number_1 - last_number_1 > best_distance:
            break

        continue_to_outer_loop = False

        n2 = n1 - 1

        while n2 > 0:
            current_number_2 = n2 * (3 * n2 - 1) // 2

            if current_number_1 - current_number_2 > best_distance:
                continue_to_outer_loop = True
                break

            if is_pentagonal_number(current_number_1 + current_number_2) and is_pentagonal_number(current_number_1 - current_number_2):
                tmp_distance = current_number_1 - current_number_2

                if best_distance > tmp_distance:
                    best_distance = tmp_distance

            n2 -= 1

        n1 += 1

        if continue_to_outer_loop:
            continue

        last_number_1 = current_number_1

    return best_distance

print(project_euler_44())

In is_pentagonal_number, I used the quadratic formula. Suppose the pentagonal number candidate is \$m\$. You want to find out whether there exists an integer \$n\$ such that $$ m = \frac{n(3n - 1)}{2} = 1.5n^2 - 0.5n. $$ Next, you substract \$m\$ from both the side, obtaining $$ 1.5n^2 - 0.5n - m = 0. $$ Solve with regard to \$n\$: if it is an integer, \$m\$ is a pentagonal number.

Hope that helps.