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

Written by on 28 May 2011

Topics: Project Euler

Problem 45 of Project Euler reads

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

TriangleTn=n(n+1)/21, 3, 6, 10, 15, …
PentagonalPn=n(3n-1)/21, 5, 12, 22, 35, …
HexagonalHn=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.

5 Comments For This Post I'd Love to Hear Yours!

  1. Imgen says:

    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);
                    }
                }
            }
        }
    
    
  2. Kristian says:

    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.

  3. Ronnie says:

    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

  4. Ritesh says:

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

  5. McLovin says:

    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…

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

Notify me of comments via e-mail. You can also subscribe without commenting.