Project Euler #45 - Triangular, pentagonal, and hexagonal 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) &amp;&amp; hex.Contains(n) &amp;&amp; n &gt; 40755){
            Console.WriteLine(n);
            return;
        }
    }
}

IEnumerable&lt;BigInteger&gt; Triangles()
{
    for(BigInteger n = 1;;n++)
    {
        yield return (n * (n + 1) / 2); 
    }
}

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

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


How can I improve this?
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 ) &amp;&amp; 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 &lt; max ) {
      tt = getTriangular(++t);
    } else if ( pp &lt; max ) {
      pp = getPentagonal(++p);
    } else if ( hh &lt; 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.