Project Euler #45 - Triangular, pentagonal, and hexagonal

Question

Project Euler Problem 45

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.

My Implementation:

I used a HashSet for fast searching. I got the right answer after experimenting with the size of the HashSet. 100000 worked for me.

void Main()
{
    var pen = Pentagonals(100000);
    var hex = Hexagonals(100000);

    foreach(var n in Triangles()){
        if(pen.Contains(n) && hex.Contains(n) && n > 40755){
            Console.WriteLine(n);
            return;
        }
    }
}

IEnumerable<BigInteger> Triangles()
{
    for(BigInteger n = 1;;n++)
    {
        yield return (n * (n + 1) / 2); 
    }
}

HashSet<BigInteger> Pentagonals(int limit)
{
    HashSet<BigInteger> set = new HashSet<BigInteger>();
    for(BigInteger n = 1;n <= limit;n++)
    {
        set.Add(n * (3 *n - 1) / 2); 
    }
    return set;
}

HashSet<BigInteger> Hexagonals(int limit)
{
    HashSet<BigInteger> set = new HashSet<BigInteger>();
    for(BigInteger n = 1;n <= limit;n++)
    {
        set.Add(n * (2*n - 1)); 
    }
    return set;
}

How can I improve this?

Answer 1

This expands my comments on Brythan's answer:

Note: It's written in JavaScript (not C#) since I haven't written C# in years but you should be able to convert it fairly easily.

Answer 1 - Test if successive hexagonal numbers are also triangular and pentagonal

A number \$c\$ is triangular if \$c = t(t + 1)/2\$ (where \$c \in \mathbb{N}\$ and \$t \in \mathbb{N}\$) which can be rewritten as \$0 = t^2 + t -2c\$ and then in terms on \$t\$, using the positive root given by the quadratic formula, as \$t = \frac{-1 + \sqrt{1+8c}}{2}\$.

Similarly, the pentagonal number formula \$c = p(3p-1)/2\$ (where \$c \in \mathbb{N}\$ and \$p \in \mathbb{N}\$) can be rewritten as \$0 = 3p^2 - p - 2c\$ then as \$p = \frac{1 + \sqrt{1+24c}}{6}\$ .

You can then use these to test successive hexagonal numbers to see if the they are also triangular and pentagonal:

function quadraticRoot(a,b,c){
  return ( -b + Math.sqrt( b*b - 4 * a * c ) ) / (2 * a);
}

function isInteger(n){
  return n === Math.round( n );
}

function isTriangularNumber(n){
  return isInteger( quadraticRoot( 1, 1, n*-2) );
}

function isPentagonalNumber(n){
  return isInteger( quadraticRoot( 3,-1, n*-2 ) );
}

function getNextHexagonalNumberWhichIsTriangularAndPentagonal(n){
  var hex;
  while( true ) {
    hex = n * ( 2 * n - 1 );
    if ( isTriangularNumber( hex ) && isPentagonalNumber( hex ) )
    {
      return n;
    }
    ++n;
  }
}

Then:

getNextHexagonalNumberWhichIsTriangularAndPentagonal( 144 );

Gives the answer 27693 as the next hexagonal number that is also triangular and pentagonal.

Answer 2 - Generate successive triangular, pentagonal and hexagonal numbers

function getTriangular(n){
  return n * (n + 1 ) / 2;
}

function getPentagonal(n){
  return n * ( 3 * n - 1 ) / 2;
}

function getHexagonal(n){
  return n * ( 2 * n - 1 );
}

function getNextEqualTriangluarPentagonalHexagonalNumbers(t,p,h){
  var tt = getTriangular(t);
  var pp = getPentagonal(p);
  var hh = getHexagonal(h);
  while ( true ){
    var max = Math.max( tt, pp, hh );
    if ( tt < max ) {
      tt = getTriangular(++t);
    } else if ( pp < max ) {
      pp = getPentagonal(++p);
    } else if ( hh < max ) {
      hh = getHexagonal(++h);
    } else {
      return [t,p,h];
    }
  }
}

Then

getNextEqualTriangluarPentagonalHexagonalNumbers(286,166,144);

Gives the answer [ 55385, 31977, 27693 ] for the next triangular, pentagonal and hexagonal numbers which are identical.

Answer 2

foreach(var n in Triangles()){

You shouldn't call this variable n. Elsewhere, you use n to mean the number that you use to generate the other numbers. You shouldn't also use it for the result. I'd name it either x (standard for an unknown value) or candidate (each value that you check is a candidate for being the one that you want).

for(BigInteger n = 1;;n++)

You don't need to start with 1 here. You could start with n = 286, as that is the next triangular number after 40,755. That will also save you having to check n > 40755 in main. You could also do the same thing with the pentagonals and hexagonals. However, we can do better than this in terms of memory.

It's possible to test directly if a number is triangular or pentagonal. So all you have to do to solve this is to generate all the hexagonal numbers starting with the 144th (the next hexagonal number after 40,755), and then test if they are triangular and pentagonal. This saves the memory to store the two HashSets.

Both these solutions should be about the same in how they grow in computation time. Your algorithm may be faster in absolute terms, as the tests are more expensive than the generation. This algorithm is better in that it only generates numbers up to the solution and doesn't require a large amount of memory. Your algorithm will run out of memory first. It's unclear if both will be computationally intractable before that happens.

If your algorithm is significantly faster, you can also adjust it to not require the HashSet storage. You can generate the pentagonals and hexagonals as you need them, saving only the largest. This is because all three sequences are strictly increasing. So once your largest triangular number is greater than your current pentagonal or hexagonal, you can forget the current one and move to the next.

I'd write some code, but I'm not really familiar with C#. Hopefully I've described the algorithms well enough that you can write the necessary code.

Answer 3

• The first thing you have to realize is that every hexagonal number is also a triangular number, so you don't have to check triangular numbers at all.
• Also, you don't need the slow BigInteger, just use long.
• Storing all numbers in a collection is not necessary, since you only need to keep one number at a time.

• You can of course use IsPentagonal(n) (as MT0 does), but I found that simply iterating over the pentagonals is a lot faster. (Math.Sqrt is slow)

  public long Solve045()
  {
      long h = 144L, p = 166L; //given as lower bounds
      long hex, penta = 0L;
      do {
          hex = Hexagonal(h++);
          while (penta < hex) penta = Pentagonal(p++);
      } while (hex != penta);
      return hex;
  }
  
  private long Hexagonal(long n)
  {
      return n * (2 * n - 1);
  }
  
  private long Pentagonal(long n)
  {
      return n * (3 * n - 1) / 2;
  }
  

You can also inline the 2 methods to keep it all in one place:

public long Solve045()
{
    long = 144L, p = 166L; //given as lower bounds
    long hex, penta = 0L;
    Func<long, long> hexagonal = n => n * (2 * n - 1),
                 pentagonal = n => n * (3 * n - 1) / 2;
    do {
        hex = hexagonal(h++);
        while (penta < hex) penta = pentagonal(p++);
    } while (hex != penta);
    return hex;
}