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, 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_{4}+ P_{7}= 22 + 70 = 92 = P_{8}. 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 is pentagonal and D = |P_{k}– P_{j}| 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.

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.

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.

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

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

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

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.

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”

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”?

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

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

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.

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=

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.

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?

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!

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

btw, thanks for ur nice post.

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.

@kmonsoor: Thanks, it is fixed now.

@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?

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

Thanks for the link, it is certainly an interesting read.

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

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??

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 🙂

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`

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

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`

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

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.

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?

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

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

// 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));

}

}

}