// youâ€™re reading...
(22 votes, average: 2.73 out of 5)
Loading ...

## Project Euler Problem 44 Solution

#### Problem Description

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

#### Analysis

When the problem asks for D = |Pk − Pj| to be minimized it simply means the smallest pair which, by our method, is the first occurrence found.

#### Solution

Runs < 1 second in Python with improvements suggested by James.

```def pe44(): ps = set() i = 0 while True: i += 1 p = (3*i*i - i) / 2 ps.add(p) for n in ps: if p-n in ps and p-2*n in ps: return p-2*n   print "Answer to PE44 = ", pe44()```

#### Comments

Also see Problem 45.

## Discussion

### 6 Responses to “Project Euler Problem 44 Solution”

1. This runs 5x as fast:

``` def pe44(): i=0 ps=[1] p=set(ps) while True: i+=1 x=(3*i*i-i)/2 ps.append(x) p.add(x) for j in range(2,len(ps)-1): if (ps[i]-ps[j]) in p and is_pentagonal(ps[i]+ps[j]): return ps[i]-ps[j]```

Posted by James | June 18, 2011, 11:25 PM
• I formatted your code for presentation and tested it – very fast. Good job and thanks for sharing your ideas.

Posted by Mike | July 12, 2011, 7:29 PM
• Hello,JAMES
Execute me. Can you explain the ‘p-2*n in ps’ meaning ? thx XD!

Posted by rookieljw | August 10, 2013, 7:41 AM
2. I totally understood James’ code

I couldn’t understand the “p-2n” part in your solution.

Maybe it’s some mathematical concept escaping me ?

Posted by hm64 | February 2, 2013, 7:08 AM
• He’s skipping the need for a square root.

Let a = p – n, b = n.

We know both p and n are prime (since they’re in the set).

a + b = (p – n) + n = p, which doesn’t need to be checked, but the other two do:
a = (p – n)
a – b = (p – n) – n = p – 2*n

If they’re both pentagonal numbers, then it’s found a difference, and returns a – b.

Posted by Matthew | September 6, 2013, 2:23 PM

### Trackbacks/Pingbacks

1. [...] Problems 44 & 45? The same logic applies except for triangle numbers. Whenever the equation √((1+8n)-1) / 2 [...]