# Project Euler 44: Find the smallest pair of pentagonal numbers whose sum and difference is pentagonal.

In Problem 42 we dealt with triangular problems, in Problem 44 of Project Euler we deal with pentagonal number, I can only wonder if we have to deal with septagonal numbers in Problem 46. Anyway the problem reads

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?

I have found a solution which I will present to you in just a few lines, but I must admit that I haven’t been able to justify why it is the right solution it gives us. The solution I have made just finds a solution to the problem which happens to the right solution.

I did not want to generate a list of pentagonal numbers, so I wanted to make a small function which checks if a given number is pentagonal by checking if the inverse function yields an integer, just like in the solution to  Problem 42. We could rather easily calculate the inverse function as we did with the inverse function for triangular numbers, or we can cheat and peak at the pentagonal number entry at Wikipedia.

The inverse function is

That enables us to make a C# function that checks if a number is pentagonal

```private bool isPentagonal(int number) {
double penTest = (Math.Sqrt(1 + 24 * number) + 1.0) / 6.0;
return penTest == ((int)penTest);
}
```

Once we have this crucial function we can make two nested loops to check pentagonal numbers until we find two where the sum and difference are pentagonal as well. I am frustrated since I can’t figure out why this one is the first. I can prove that it is indeed minimal by testing other numbers until the difference of two numbers reach the result of this problem. However I haven’t done that.

The outer loop of the algorithm counts upwards generating and the inner loop counting downwards testing all pentagonal numbers less than the one generated by the outer loop. The code looks like

```int result = 0;
bool notFound = true;
int i = 1;

while (notFound) {
i++;
int n = i * (3 * i - 1) / 2;

for (int j = i-1; j > 0; j--) {
int m = j * (3 * j - 1) / 2;
if (isPentagonal(n - m) && isPentagonal(n + m)) {
result = n-m;
notFound = false;
break;
}
}
}
```

and gives the result

```k = 2167, j = 1020
The value of D is 5482660
Solution took 35 ms
```

## Wrapping up

I can see that many other people also can’t give the definitive answer to why the result is correct. If you understand the problem better than I do, please let me know exactly why I find the right solution.

You can as usual find the source code for the problem here.

### Posted by Kristian

jack

Sorry I know this is an old entry, but stumbled upon it.

The reason the answer is correct, is because of the nature of the series of pentagonal numbers.

If you’re calculating the pentagonal number P(n) as (3n^2 – n)/2, you’ll notice that the difference between P(n) and P(n-1) increases as n increases.

For example, P(2) – P(1) = 4.
P(3) – P(2) = 7.

This means that once you reach a certain number x, P(x) – P(x-1) > 5482660.

If the difference between P(x) – P(x-1) is greater than 5482660, then no pentagonal number greater than P(x-1) can be involved in a pair for which the value of D is less than 5482660.

At this point, you know that 5482660 is the lowest value of D that can be achieved.

Kristian

Hi Jack

I believe you are right and thanks for that input. However, I don’t think the current algorithm will actually test enough numbers in order to rule out other options. I think x needs to be rather large before we reach P(x)-P(x-1) > 5482660.

Divye Kapoor

I was working through the same problem and though I haven’t read through your solution to avoid spoilers, you might be interested in my derivation of a faster test for Pentagonality of numbers. Have a look at http://www.divye.in/2012/07/how-do-you-determine-if-number-n-is.html

Kristian

Thanks for the link. It seems like a good explanation and something new for me. I will definitely have to study it in greater detail later on.

/Kristian

Imgen

I have a better solution which will indeed give a definitive answer, code as below. This solution is not based on haunch or guess.

```//Analysis:
//Since we D is a pentagonal itself, we can loop thru the Pn and find the first pentagonal number
//that meets that exists another Pm with Pm > Pn and (Pm + Pn) / 2, (Pm - Pn) / 2 are also
//pentagonal
//Further so, let a = Pm, b = Pn, let D = |a - b|, S = a + b
//Then we can deduce that
//D < a < S, b < a < S
//a = D + b, S = D + 2b

namespace Problem44
{
class Program
{
static ulong CalcPn(ulong n)
{
return n * (3 * n - 1) / 2;
}

static ulong EsstimatePentagonalIndex(ulong pn)
{
ulong delta = (ulong)Math.Sqrt(24 * pn + 1);
return (delta + 1) / 6;
}

static bool IsPendagonal(ulong pn)
{
ulong index = EsstimatePentagonalIndex(pn);
return CalcPn(index) == pn;
}

static void Main(string[] args)
{
var stopwatch = new Stopwatch();
stopwatch.Start();
//First we assume that D >= b
for (ulong dIndex = 1; answer == 0; dIndex++)
{
ulong d = CalcPn(dIndex);
for (ulong bIndex = 1; bIndex <= dIndex; bIndex++)
{
ulong b = CalcPn(bIndex);
ulong a = d + b, s = a + b;
if (IsPendagonal(a) && IsPendagonal(s))
{
break;
}
}
}

//Then we assume D < b
for (ulong bIndex = 1; ; bIndex++)
{
ulong b = CalcPn(bIndex);
ulong minD = CalcPn(bIndex + 1) - b;
{
break;
}
ulong minDIndex = EsstimatePentagonalIndex(minD);
for (ulong dIndex = minDIndex; dIndex < bIndex; dIndex++)
{
ulong d = CalcPn(dIndex);
ulong a = d + b, s = a + b;
if (IsPendagonal(a) && IsPendagonal(s))
{
break;
}
}
}
stopwatch.Stop();
Console.WriteLine("Time spent is " + stopwatch.ElapsedMilliseconds + "ms");
}
}
}
```
Kristian

Thanks for that piece of code. I know you have written your analysis in the beginning of the code, but it would be great if you could say a little more about it.

Mukund

Hi Kristian,
Java code,Running time 0.02 seconds
The important point to ponder on was to find out when it could be definitely said that a pentagonal difference was the minimum one.A definite answer to this is when the “Differences between P(x) and each of the nos less than P(x) are all higher than the Pentagonal difference we just found.Because that way there is no chance of a lower difference being found”

```import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class ProblemFortyFour
{
public static void main(String[] args)
{
long starttime=System.currentTimeMillis();

boolean continueFlag=true;
Map setOfPentagons=new HashMap();
setOfPentagons.put(1, 1);
while(continueFlag)
{
continueFlag=false;
Pn=(no*(3*no-1))/2;

setOfPentagons.put(no,Pn);
for(int i=no-1;i>0;i--)
{
diff=setOfPentagons.get(no)-setOfPentagons.get(i);

{

if((int)cal==cal)
{

if(diff>minDiff||minDiff==0)
{

minDiff=diff;

}

}

}

}
if(diff<minDiff||minDiff==0)
{

continueFlag=true;
}

++no;
}

System.out.println("final difference:"+minDiff);
long endtime=System.currentTimeMillis();
System.out.println(endtime-starttime+" ms");

}

}
```
Kristian

Hi Mukund

Thanks for posting your code. Yes that would be a correct way of checking if we have found the minimum. So you need to generate numbers until two consecutive numbers have a distances larger than the best solution. Does that make long in your code compared to just finding “a solution”?

Mukund

No it is not a significant difference.It takes a few ms extra thats it.

Kristian

Ok, that’s interesting. Thanks for the clarification.

[…] shabby. If I wasn’t so fond of storing things in arrays and just checking some values like this guy does, then I bet it would be much […]

Paul

Kristian,
The Python code below works. You can see it in action with prove=True and printit=10000. Finding the solution takes about 0.2 secs, but proving it takes about 250 secs. The proving takes much more time as finding the solution, so anyone claiming to do that in a few msec has some explaining to do, I think. Of course using C the times can be a lot lower.

```sqrt = math.sqrt

def pe44(prove=False, printit=0):
""" D, a, b, S are pentagon numbers
a + b  = S
|b- a| = D
phase 1: search for a solution (0.2 s) -> min_D
given D, b -> test a = b - D and S = 2 * b - D
a < b < S, D < b < S in the method below
a may be larger or smaller than D, but is positive
As a < b, we can test if a in pentagonals.
S is larger than b and we have to use is_pent
If prove is True then phase 2 proves that there is no solution with
a D lower than min_D:
phase 2: try to find a solution with a lower D
if D is smaller than b - b_prev it can be removed from Ds
search stops if D < b - b_prev for all D in Ds (Ds is empty)
total time 250 sec. In C this should be only a few secs.
"""
def pent(n): return n * (3 * n - 1) // 2
def is_pent(N): return ((sqrt(24 * N + 1) + 1) / 6.0).is_integer()
ps = set() # keeps pentagonal numbers smaller than b
Ds = []    # keeps the list of possible D
min_D = 0
b = 0
for b_index in count(1):
b_prev = b
b = pent(b_index)
delta = b - b_prev
# any D smaller than delta can be removed, as a=b-D cannot be pentagonal
if Ds and Ds[0] < delta:
Ds.pop(0)
if printit and b_index % printit == 0:
print b_index, clock() - t0, len(Ds)
# if min_D is found and no Ds we can stop
if min_D and not (prove and Ds):
break
for D in Ds:
if b - D in ps and is_pent(2 * b - D):
min_D = D
while Ds[-1] >= min_D: # from now on only check D < min_D
Ds.pop()
break
if not min_D:
Ds.append(b)
return min_D
```
Kristian

Hi Paul

Thanks for the code. I will try to run it and study it a bit more at some point. I just need to get Python up and running.

I take it you are implying that Mukund’s code does indeed not prove that it is the smallest such number? Or at least that he has some explaining to do in order to convince you. I have heard that statement before, but not backed by code like you do here. So very much thanks for that code.

And regarding the C vs. interpreted languages. I have seen comparisons of Java and C at some point (Unfortunatly, haven’t been able to find the article again). Where the java code was only a few percent slower when they were both optimized. So I am a strong believer that, yes C will be faster, but not necessarily much, and especially if you use the right algorithms rather than brute forcing (and now I will step down from the soap box again=

Paul

Hi Kristian,

I translated Mukund’s code into Python. It took about 2 secs to come up with the first value for D and then immediately after that it reports that as the solution. It does not take any time to go to higher values for b. Considering that the solution has an index of 2167 for b and that the check has to go to a b value of about 1820000, then it makes sense that it takes some time to check it.

Kristian

Thanks for that explanation it makes sense. In general I just love my readers, since they take the time to dig into stuff that I don’t get the time for myself.

Why is the answer not Pj: 1820 Pk: 2262 Pj – Pk = 442 and Pj + Pk = 4802??? What am I missing here?

Kristian

Because 442 is not a pentagonal number.

Okay I see now I had a slight problem with my check algorithm. I got it right. Thanks for this website, it is a God send and extremely helpful!

kmonsoor

The hyperlink at “solution to Problem 42.” has a little flaw. It has repeated “http” …

btw, thanks for ur nice post.

Gary Walker

There is a huge optimization that I overlooked for quite a while on this. Once you find the first dual prime, the difference becomes the maximum difference that you ever need to examine again.

So in the inner loop, evaluate from i = (n-1) down to 1. But, if Pn – Pi > MinDiff, you can perform an early exit from the loop. As n grows, the number of iterations in the innner loop shrinks rapidly.

With this optimization, the “proving version” that stops the outer loop when 3n-3 > mindiff ran in 7 seconds on my PC.

Kristian

@kmonsoor: Thanks, it is fixed now.

Kristian

@Gary: That seems to make sense. At least the first part. I am not sure I can follow the second part. Can you post the code for it?

dominique

Hello, thank you for your contributions. A short link which you might like, even though it does not bring any specific light to the specific related Euler problem: http://www.fq.math.ca/Scanned/8-1/hansen.pdf

Kristian

Fluttert

Thnx for all insights behind algorithms 🙂 Whenever I solve a Project-Euler question, I just have to check this site for additional optimizations.

I didnt think of your isPentagonal-function.
Instead used 2 dictionaries: {i, P(i)}, and {P(i), i}
When a difference is encountered just check if the key in dictionary {P(i),i} exists (lookup time = O(1), same as hashtable)

The rest is pretty the same 🙂

Complete code on Github Gist

Tweet-he-twat

the same solution takes 10 seconds to run in python.
I know python is a little slow compared to others, but your’s only take 24ms??

Michiel

Hi everyone,
With my code it does take way to much time to evaluate the answer, but it gives the right answer for sure because it loops through the triangle numbers in a different way.
The problem states 4 triangle numbers, lets call them Pi, Pj, Pk and Pl. (Where Pi=D) Now, Pj-Pk=Pi gives Pi+Pj=Pk and Pj+Pk=Pl. To find the lowest value for Pi, I loop through ‘i’ and ‘j’:

for(int i = o; !found; i++)
Pi=i*(3i-1)
for(int j = 0; etc…

Then Pk gets evaluated by Pi+Pj=Pk, and Pl by Pj+Pk=Pl. The rest does pretty much the same as your code, but after 10 minutes waiting for the answer, I know for sure it is the right answer 🙂

Gary Walker

Sorry, failed to subscribe, so I did not notice you asked for my code earlier.

This optimization only helps the proving version, but it was a huge difference. Main body in python, with comments re: the optimization.
``` def main():```

``` # avoid recalcs and need for reverse pentagonal algorithm p = [None, 1] # list of pentagonal values (indexed) pdic = {1:1} # dictionary of pentagonal values (hashed) def pentagonal(num): if (num <= 0): raise ValueError("must be positive integer") n= len(p) if (num < n): return p[num] while (n p[-1]): pentagonal(len(p)) return n in pdic min_diff = 10**100 # start with a really bound on difference ii = 2 while True: pii = pentagonal(ii) if (pii - pentagonal(ii-1)) > min_diff: print("No more possible smaller min_diff values") break # optimization part 1 -- count down instead of up for jj in range(ii-1,0,-1): pjj = pentagonal(jj) # optimization part 2 -- because we are counting down # we can do a early exit when the difference has grown # too large for this iteration, i.e., (abs(diff) will # continue to grow as pjj decreases towards 1 if (pii - pjj > min_diff): break if is_pentagonal(pii-pjj) and is_pentagonal(pii+pjj): # detected a "pentagonal pair" if (pii-pjj < min_diff): min_diff = pii - pjj print("a new min_diff", min_diff) ii += 1 ```

``` return min_diff ```

Gary Walker

Sorry, failed to subscribe, so I did not notice you asked for my code earlier.

This optimization only helps the proving version, but it was a huge difference. Main body in python, with comments re: the optimization.

def main():

# avoid recalcs and need for reverse pentagonal algorithm
p = [None, 1] # list of pentagonal values (indexed)
pdic = {1:1} # dictionary of pentagonal values (hashed)

def pentagonal(num):
if (num <= 0):
raise ValueError("must be positive integer")
n= len(p)
if (num < n):
return p[num]

while (n p[-1]):
pentagonal(len(p))
return n in pdic

ii = 2
while True:
pii = pentagonal(ii)
if (pii – pentagonal(ii-1)) > min_diff:
print(“No more possible smaller min_diff values”)
break

# optimization part 1 — count down instead of up
for jj in range(ii-1,0,-1):
pjj = pentagonal(jj)

# optimization part 2 — because we are counting down
# we can do a early exit when the difference has grown
# too large for this iteration, i.e., (abs(diff) will
# continue to grow as pjj decreases towards 1
if (pii – pjj > min_diff):
break

if is_pentagonal(pii-pjj) and is_pentagonal(pii+pjj):
# detected a “pentagonal pair”
if (pii-pjj < min_diff):
min_diff = pii – pjj
print("a new min_diff", min_diff)
ii += 1

return min_diff

Gary Walker

3rd attempt — a preview option would be nice 🙂

``` def main():```

``` # avoid recalcs and need for reverse pentagonal algorithm p = [None, 1] # list of pentagonal values (indexed) pdic = {1:1} # dictionary of pentagonal values (hashed) def pentagonal(num): if (num <= 0): raise ValueError("must be positive integer") n= len(p) if (num < n): return p[num] while (n p[-1]): pentagonal(len(p)) return n in pdic min_diff = 10**100 # start with a really bound on difference ii = 2 while True: pii = pentagonal(ii) if (pii - pentagonal(ii-1)) > min_diff: print("No more possible smaller min_diff values") break # optimization part 1 -- count down instead of up for jj in range(ii-1,0,-1): pjj = pentagonal(jj) # optimization part 2 -- because we are counting down # we can do a early exit when the difference has grown # too large for this iteration, i.e., (abs(diff) will # continue to grow as pjj decreases towards 1 if (pii - pjj > min_diff): break if is_pentagonal(pii-pjj) and is_pentagonal(pii+pjj): # detected a "pentagonal pair" if (pii-pjj < min_diff): min_diff = pii - pjj print("a new min_diff", min_diff) ii += 1 ```

``` return min_diff ```

Jean-Marie Hachey

Results in Table 1 were obtained by running Kristian’s code (1) after adaptions for each specified polygon.

http://img11.hostingpics.net/pics/760878pe44fig1polygonal.jpg

___

Sources:
1) PE44, Kristian’s algorithm
http://www.mathblog.dk/files/euler/Problem44.cs
2) Inverse Function Calculator
http://www.numberempire.com/inversefunctioncalculator.php
3) Microsoft Visual C# 2010 Express
4) Microsoft Office Excel (2007)
5) Triangle (Triangular) numbers
http://en.wikipedia.org/wiki/Triangular_number
6) Square numbers
http://en.wikipedia.org/wiki/Square_number
7) Pentagonal numbers
http://en.wikipedia.org/wiki/Pentagonal_number
8) Hexagonal numbers
http://en.wikipedia.org/wiki/Hexagonal_number
9) Heptagonal numbers
http://en.wikipedia.org/wiki/Heptagonal_number

Trystan

If you look at the progression of the difference between P(x) and P(x-1), it starts out at 4, then goes 4 + 3n (4,7,10,…) n would be x-2. To find the 2 whose difference is 5482660, subtract 4 then divide by 3 = 1827552. That’s the 1,827,553rd and 1,827,554th number or 5,009,929,520,597 – 5,009,924,037,937.

Maci

Could I ask you why don’t you sum the numbers instead of subtract them?

So you will use A, B, A+B, 2*A+B

Is it a stupid idea?

helpYou

Here is my implementation (I break it only when the difference between 2 consecutive numbers is bigger than the found difference):

```public class P44 {

public static void main(String[] args) {
long start = System.nanoTime();
int i = 1;
int diffPos = 0;
long diffPentagonal = Long.MAX_VALUE, diff;
long nr1, nr2;
while (true) {
nr1 = i * (3 * i - 1) / 2;
if (diffPentagonal &lt; 3*(i-1) + 1) {
break;
}
int min = diffPos==0?1:i-diffPos;
for (int j = i - 1; j &gt;= min ; j--) {
nr2 = j * (3 * j - 1) / 2;
diff = nr1 - nr2;
if (diff &lt; diffPentagonal &amp;&amp; isPentagonal(diff)
&amp;&amp; isPentagonal(nr1 + nr2)) {
diffPos = i-j;
diffPentagonal = diff;
break;
}
}
i++;
}
System.out.println(diffPentagonal);
long stop = System.nanoTime();
System.out.println((stop - start) / 1000_000_000 + &quot; s&quot;);
}

private static boolean isPentagonal(long x) {
double n = (1 + Math.sqrt(1 + 24 * x)) / 6;
if (n == (long) n) {
return true;
}
return false;
}

}
```
helpYou

I forgot to mention that I increase the minimum value for j (because the difference between v[i] and v[j] increases and values that are bigger than the minimum are not important). The solution take 18 seconds.

Imaculate

I used the java code below and I got j =22, k =29 an D = 532, which passes the sum and difference test, can anyone point to me what is wrong with it?
D is minimum , right?

public class Problem44{
public static void main(String[] args){

int D = 0;
outer:for(int j = 1; j< 300; j++){
for(int k = j+1; k< 300; k++){
if(check(j,k, true) && check(j,k, false)){
int Pk = (int)(3*Math.pow(k,2) – k)/2;
int Pj = (int)(3*Math.pow(j,2) – j)/2;

D = Pk-Pj;
System.out.println("j = " +j + "k = " + k);
break outer;
}

}
}
System.out.println(D);

}

public static boolean check(int j, int k , boolean sum){
if(sum)
{
int temp = (int)(36*Math.pow(j,2) + 36*Math.pow(k,2) – 12*k – 12*j + 1);
if(Math.pow(temp, 0.5) – (int)(Math.pow(temp, 0.5)) == 0)
return true;

}else{
int temp = (int)(36*Math.pow(k,2) – 36*Math.pow(j,2) – 12*k + 12*j +1);
if(Math.pow(temp, 0.5) – (int)(Math.pow(temp, 0.5)) == 0)
return true;

}
return false;
}
}

hi do you know this equation: the difference between two numbers is 2. their is 44. what are two numbers?

Marek Paps

// More Java 8 hipster look 🙂 – lambdas and Functions

Function isPentagonal = i -> {
Double d = (1.0 + Math.sqrt(1 + 24 * i)) / 6.0;
return i == 0 ? false : d == d.intValue();
};

Function calcPentagonal = i -> i * (3 * i – 1) / 2;

BinaryOperator sumAndMinus = (a, m) -> isPentagonal.apply(a + m) ? (isPentagonal.apply(m – a) ? 1 : 0) : 0;

boolean found = false;
for (int i = 2; found == false; i++) {
//wieksze p1
log.info(“iterate:”+i);
Integer p1 = calcPentagonal.apply(i);
for (int k = i – 1; k > 0 && !found; k–) {
//mniejsze p2
Integer p2 = calcPentagonal.apply(k);
found = sumAndMinus.apply(p2, p1) == 1 ? true : false;
if (found) {
log.info(“found i:” + i + “|k:” + k);
log.info(“found P1:” + p1 + “|P2:” + p2);
log.info(“found P1 – P2 :” + (p1 – p2));
}
}
}

Ccile

Hi, a long time after the first post … I know.

But I want to post my algorithm which is different from the one I read, but the code is not faster.

You search for D pentagonal so let D be pentagonal : D = penta(i).
Now you want to have K pentagonal in this way : D + K (=J) is pentagonal and D + 2*K (=S) is pentagonal too. ( J – K = D and J + K = S )

You want to have the minimal D, so K has to be gretter than D. You will search for D = penta(j) with j > i.
Now you have a part of the algorithm in mind : D = penta(i) with i = 1, K = penta(j) with j=i+1, i+2, i+3 and so one and everytime you check if D + K and D + 2K are pentagonal. Now the question is about the “so one”. When do you change your K (or your i) ?

A interesting propertie of the pentagonal numbers is that Diff(n) = P(n+1) – P(n) is increasing. So when D + K is smaller than penta(j+1) (the first pentagonal number just after K) you know that D is not your answer and you can move to the next one.

Thanks for reading, sorry for the mistakes. (I don’t write the code because I think it’s enough to write by itself or just take another code)

2167 & 1020 in not pentagon numbers.

my pentagon list= 1 , 5 , 12 , 22 , 35 , 51 , 70 , 92 , 117 , 145 , 176 , 210 ,
247 , 287, 330, 376, 425, 477, 532, 590, 651, 715, 782, 852, 925, 1001 , 1080, 1162, 1247, 1335, 1426, 1520, 1617, 1717, 1820, 1926, 2035, 2147, 2262, 2380, 2501, 2625, 2752, 2882, 3015, 3151, 3290, 3432, 3577, 3725, 3876, 4030, 4187.

Mark

F# version, can be copied and entered directly into the FSI window in Visual Studio and run. Uses recursion, rather than typical loops. This was fun and very educational.

```let pen x =
(1. + 24. * x |> sqrt |> (+) 1.) / 6.
|> fun t -> round t = t, x

#time
let findAll =
let rec f k =
match k * (2.*k-1.) |> pen with
| false, _ -> f (k+1.)
| true, x -> int x
f 144.
#time
```
Mark

Sorry, I meant for this comment to be on question 45, I will copy there.

Måns Nilsson

In the general case I don’t think your algorithm is correct. As you point out yourself, there is the possibility that you may encounter a higher upper term and a higher lower term such that their difference is less than what you’ve already found; you need to keep checking until you’ve encountered a pair of pentagonal numbers pn and p(n-1) such that their difference is greater than the current found one. This is efficiently enough done by storing a lower limit on the lower term and updating it once you’ve found a higher term whose difference to the current upper term is not less than the current found difference. I did this and the computation time was 1 second.