Project Euler problem 44: sums and differences of pentagonal numbers

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)

• You might be interested in this question and its answers. Jul 5, 2017 at 16:20

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.

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$?
• A partial answer to your two questions is that the difference between two consecutive numbers keeps growing - at some point you have a pair with a smaller difference than any possible pair including larger numbers. Likely 3001 and 3010 are magic numbers knowable only by knowing the answer though. Jun 29, 2017 at 10:30
• @JollyJoker, I try to approach codereview.stackexchange in a similar style to what I'd use in an in-person code review, and asking the author of the code to explain it is a tool which I consider important both from a didactic point of view (helping them to understand why and how the code might need improvement) and from a psychological point of view (reinforcing that the code review is a collaboration to ensure code quality, not an oppressive roadblock). Jun 29, 2017 at 10:48
• I think you just explained why I wrote the comment, too ;) Jun 29, 2017 at 11:17

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.