# Project Euler 45: After 40755, what is the next triangle number that is also pentagonal and hexagonal?

Problem 45 of Project Euler reads

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

 Triangle Tn=n(n+1)/2 1, 3, 6, 10, 15, … Pentagonal Pn=n(3n-1)/2 1, 5, 12, 22, 35, … Hexagonal Hn=n(2n-1) 1, 6, 15, 28, 45, …

It can be verified that T285 = P165 = H143 = 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. ### Posted by Kristian Imgen

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

```    class CalculateUnit
{
public ulong Value, Index;
public Func<ulong, ulong> Calculator;

public CalculateUnit(ulong value, ulong index, Func<ulong, ulong> calculator)
{
Value = value;
Index = index;
Calculator = calculator;
}
}

class Program
{
static ulong CalcTn(ulong n)
{
return n * (n + 1) / 2;
}
static ulong CalcPn(ulong n)
{
return n * (3 * n - 1) / 2;
}
static ulong CalcHn(ulong n)
{
return n * (2 * n - 1);
}

static void Main(string[] args)
{
ulong hIndex = 144, pIndex = 166, tIndex = 286;
var calcUnits = new[]
{
new CalculateUnit(CalcHn(hIndex), hIndex, CalcHn),
new CalculateUnit(CalcPn(pIndex), pIndex, CalcPn),
new CalculateUnit(CalcTn(tIndex), tIndex, CalcTn),
};
var stopwatch = new Stopwatch();
stopwatch.Start();
while(true)
{
var firstValue = calcUnits.First().Value;
if(calcUnits.All(x => x.Value == firstValue))
{
stopwatch.Stop();
Console.WriteLine("The answer to PE45 is " + firstValue);
Console.WriteLine("Time spent is " + stopwatch.ElapsedMilliseconds + "ms");
break;
}

ulong minXn = calcUnits.Min(x => x.Value);
ulong maxXn = calcUnits.Max(x => x.Value);
var minCalcUnit = calcUnits.First(x => x.Value == minXn);
while(minCalcUnit.Value < maxXn)
{
minCalcUnit.Index++;
minCalcUnit.Value = minCalcUnit.Calculator(minCalcUnit.Index);
}
}
}
}

``` Kristian

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

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,

```def P(n):
return (n*(3*n-1))/2

def H(n):
return (n*(2*n-1))

i=144; j=166
got_it=False
while not got_it:
hexz=H(i)
i+=1
while 1:
pen=P(j)
if pen<hexz:
j+=1
elif pen>hexz:
break
else:
print pen
got_it=True
break
```

Ran in 0.080s which is 80ms on a 2.4GHz Pentium B980.
surely would run a bit faster in Compiled Languages Ritesh

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;
} McLovin

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… mrb

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.

```int main(){
int p=165,h=143;
long long P=40755,H=40755;

while(1==1){
p++;
P += 3*p - 2;
if(H&lt;P){
h++;
H += 4*h - 3;
}
if(P==H){
return 0;
}
}
}
```

That’s all Julian

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

“`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 formatting seems to be amiss. Mark

```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.``` Mark

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 Satya shivam

#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,b,x;
for(i=1;i<=1000000;i++)
{
a[i]=(i(i+1))/2;
}
for(i=1;i<=1000000;i++)
{
b[i]=(i
(3*i-1))/2;
}
for(i=1;i<=1000000;i++)
{
x=search(0,1000000,a,b[i]);
if(x>0)
cout<<x<<endl;
}
return 0;
}