Problem 042

Project Euler

Coded triangle numbers

Problem 42

The nth term of the sequence of triangle numbers is given by, tn = ½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 = t10. 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?

This problem uses the same word value in problem 22. We first calculate a list of triangle number. Assume there is no word over 30 characters, the largest triangle number should not be greater than 26*30=780. From the formula, we know that

780 * 2 = 1560 = n (n+1)
n \approx \sqrt(1560) \approx 40

We calculate a list of triangle number up to 40. The rest is just to nest two loop, outside looping the words, inside looping through triangle numbers and count the number of triangle words.