Problem 45 of Project Euler reads

Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:

TriangleT_{n}=n(n+1)/21, 3, 6, 10, 15, …PentagonalP_{n}=n(3n-1)/21, 5, 12, 22, 35, …HexagonalH_{n}=n(2n-1)1, 6, 15, 28, 45, …

It can be verified that T_{285}= P_{165}= H_{143}= 40755.

Find the next triangle number that is also pentagonal and hexagonal.

This is actually a pretty easy problem to solve since we have already made the major part of the code in the solution to Problem 44.

The first thing to note is that the set of hexagonal numbers is a subset of triangle numbers if we substitute n = 2m – 1 into the triangle number equation we get

Which indeed is the formula for hexagonal numbers. That means all triangular number based on an odd n is a hexagonal numbers.

So if we generate hexagonal numbers and check if they are pentagonal numbers at some point we will find the answer. The C# code for that looks like

long result = 0; int i = 143; while (true) { i++; result = i * (2 * i - 1); if (isPentagonal(result)) { break; } }

The code is pretty simple since to write since the isPentagonal method already exists. The only thing that tricked me was that I used an integer to store the result rather than a long. Once I chanced that the solution ran rather smoothly. The result was

The next triagonal, pentagonal and hexagonal number is 1533776805 Solution took 1 ms

## Wrapping up

There isn’t much to say about this problem, I think it was rather easy to solve especially once the inverse function has already be derived. Comments, questions, other solutions or errors are as always welcome. I would love to get some feedback.

You can download the source code here if you want to have the full piece of code for inspiration.

My code, although a bit longer, but I think it’s the most efficient. The basic idea is to let the largest of the Pi, Tj, Hk wait until the smallest of the 3 catches up

Thanks for an alternative approach, I love getting input that I haven’t thought of. I haven’t tested the complexity of your code compared to mine. So I will take your word for it. However, both are pretty fast.

Hello Kristian, I think I am commenting on third or fourth sum here,

Actually I check your solutions when I finished mine, it gives me some idea what are the other ways.. since ur solutions are of high quality

here, since I found nothing to check isPentagonal except caching the results, and I didn’t want to do that (I feel like brute-ing)

I checked H(n) for every value, then started calculating P(x) from where I left it,

I know, many may not have got what I said

have a look at my code,

Ran in 0.080s which is 80ms on a 2.4GHz Pentium B980.

surely would run a bit faster in Compiled Languages

So , a nice thing to observe for the triangle numbers is that:

Let the triangle number be x. Then , the product of the floor of integer corresponding to the square root of twice the triangle number and the next number is the triangle number instead . And since , every odd triangle number is a hexagonal number , we can check for triangularity along with the “odd” part as we check.

And this check is faster than check for Pentagonal Numbers , it is faster than your code.

Here is my code:

#include

#include

#include

using namespace std;

clock_t begin , end;

double time_spent;

bool check(long int a){

a = 2*a;

long int now = pow(a , 0.5);

if(now%2 != 0 && now*(now+1) == a){

return true;

}

return false;

}

int main(){

int count = 0;

begin = clock();

for(long int i = 2; i < 1000000 ; i++ ){

long int here = i*(3*i – 1)/2;

bool val = check(here);

if(val == true){

count++;

if(count == 2){

cout << here << endl;

goto BLOCK;

}

}

}

BLOCK:

end = clock();

time_spent = (double)(end – begin)/CLOCKS_PER_SEC;

cout << time_spent << endl;

return 0;

}

This program is not that hard. All you need is large int arrays, 3 instantiation loops, and a nested loop that takes O(n3) time with an if statement determining if the indexes of the large arrays are all equal.

granted, it is one of those programs where its like, “compile and go make a sandwich, then go beat halo Combat Evolved five times in a row, but it serves its purpose… A lot of these programs look like an overkill. Lots of unneeded methods, and uses of primitive data types that aren’t required, but in a sense, make sense to have (for safety purposes). That’s just me though…

This one runs in 0 ms. (in C)

I took a different approach. First I derived the increment for each number, and I used that every hexagonal number is a triangle number which you mentioned.

P_n – P_{n-1} = 3*n – 2

H_n – H_{n-1} = 4*n – 3

Then increment the P with every step, and increment H when it is less than P, until they coincide.

That’s all

This is my solution. I did not see, that the pentagonals are a subset of the triangles, so I checked for both.

Nevertheless my code runs in 0 ms. Language is “Java”.

public class P_045_TriangularPentagonalAndHexagonal extends EulerProblemObject {

@Override

protected void processProblem() {

int hexN = 143; //

int p = 0;

boolean foundIt = false;

while(!foundIt){

hexN++;

p = this.getNthHexagonal(hexN);

if(this.isPentagonal(p) && this.isTriangle(p)){

foundIt = true;

}

}

this.appendMsgln(“The next triagonal, pentagonal and hexagonal\nnumber after 40755 is: ” + p);

}

private int getNthHexagonal(int n){

return (2*n*n-n);

}

private boolean isPentagonal(int p){

/*

Inverse function: -> n

p = n(3n-1)/2 | *2

2p = 3n^2-n | *3

6p = 9n^2-3n | + (1/2)^2 -> 1/4

6p+(1/4) = [9n^2-2]*[(1/2)*3*n]+[(1/2)^2]

6p+0.25 = (3n-(1/2))^2 | sqrt

sqrt(6p+0.25) = 3n-0.5 | + 0.5

sqrt(6p+0.25)+0.5 = 3n | : 3

(sqrt(6p+0.25)+0.5)/3 = n

*/

double n = ((double)p)*6.0d+0.25d;

n = (Math.sqrt(n)+0.5d)/3.0d;

return (n%1 == 0.0d);

}

private boolean isTriangle(int t){

/*

Inverse function: -> n

t = (n*n+n)/2 | *2

t*2 = (n*n)+n | +(1/2)^2

t*2+(1/4) = (n+1/2)^2 | sqrt

sqrt(t*2+0.25) = n+0.5 | -0.5

sqrt(t*2+0.25)-0.5 = n

*/

double n = ((double)t)*2.0d+0.25d;

n = Math.sqrt(n)-0.5d;

return (n%1 == 0.0d);

}

}

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“`

“`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“`

sorry formatting seems to be amiss.

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

let findAll =

let rec f k =

match k * (2.*k-1.) |> pen with

| false, _ -> f (k+1.)

| true, x -> int x

f 144.

See here for correct code snippet with pertinent whitespace, having problems formatting code in comments: http://www.mathblog.dk/project-euler-44-smallest-pair-pentagonal-numbers/#comment-1641905

#include

#include

using namespace std;

long long int search(long long int l,long long int r,long long int a[],long long int val)

{

while(l<=r)

{

long long int mid=(l+r)/2;

if(a[mid]==val)

return val;

else if(a[mid]>val)

r=mid-1;

else l=mid+1;

}

return -1;

}

int main()

{

long long int i,a[1000004],b[1000004],x;

for(i=1;i<=1000000;i++)

{

a[i]=(i

(i+1))/2;(3*i-1))/2;}

for(i=1;i<=1000000;i++)

{

b[i]=(i

}

for(i=1;i<=1000000;i++)

{

x=search(0,1000000,a,b[i]);

if(x>0)

cout<<x<<endl;

}

return 0;

}