Project Euler Solution #42: Coded triangle numbers

The n^th term of the sequence of triangle numbers is given by, t_n = ½n(n+1); so the first ten triangle numbers are:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 = t₁₀. If the word value is a triangle number then we shall call the word a triangle word.

Using words.txt (right click and 'Save Link/Target As...'), a 16K text file containing nearly two-thousand common English words, how many are triangle words?

Solution

The mechanics are quite similar to Problem 22, but I'll solve it a bit different this time. However, the real difference is that we need to check each word for a certain criterion and count on that.

Okay, we first need to read in the contents and remove the quotes:

<?php
$cont = file_get_contents("https://projecteuler.net/project/resources/p042_words.txt");
$cont = str_replace('"', '', $cont);

All that is missing is summing a boolean function isTriangular($word):

$c = 0;
foreach (explode(',', $cont) as $word) {
  $c+= isTriangular($word);
}
echo $c;

Okay now to the interesting part. How can we check if a word is a triangular word. First we need to sum over it's ASCII values and after that we use the inverse of the given formula to check if the result is an integer. That means we solve \(t_n = n(n+1)/2\) for \(n\) and ignore the negative solution:

\[\begin{array}{rrl} & t_n =& \frac{1}{2}n(n+1)\\ \Leftrightarrow & 2t_n =& n^2+n\\ \Leftrightarrow & 2t_n+\frac{1}{4} =& (n+\frac{1}{2})^2\\ \Leftrightarrow & \sqrt{2t_n+\frac{1}{4}}-\frac{1}{2} =& n\\ \Leftrightarrow & \frac{1}{2}(\sqrt{8t_n +1}-1) =& n\\ \end{array} \]

All we need to do is to check if \(n\) is an integer. We could use fmod to do this or simply chop off the fractional places. When the original positive number \(n\) is equal to the floored value, we know the number must be an integer:

function isTriangular($word) {
  $l = strlen($word);
  $s = 0;
  for ($i = 0; $i < $l; $i++) {
    $s+= ord($word[$i]) - 64;
  }
  $n = (sqrt(8 * $s + 1) - 1) / 2;
  return $n == (int)$n;
}