Project Euler 42 Problem Statement

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, a 16K text file containing nearly two-thousand common English words, how many are triangle words?


We can use some of our understanding from Project Euler 22 to parse and process the list of words (included in the REPL.IT files tab as words.txt). But first, we need to find a way to determine if a number is a triangle number.

If we solve the triangle formula for n then we can test numbers for being a triangle number. Since this is a quadratic equation, we will use the quadratic formula to solve for n.

The quadratic formula:


Let’s put the triangle equation into a recognizable quadratic form using algebra.

t_n = \frac{n(n+1)}{2}
2t_n = n^2 + n

n^2 + n - 2t_n = 0

Using the quadratic formula to solve for n with coefficients: a = 1, b = 1, and c = -2tn

n = \frac{\sqrt{1 + 8t_n} - 1}{2}

This codes in Python as a lambda function:

is_tn = lambda t: (sqrt(1 + 8*t) - 1) / 2 % 1 == 0

Given t, if our expression evaluates to an integer then the number is a triangle number. Only integers mod 1 will evaluate to 0.

Next, the quotation marks (“) are removed by ignoring the first and last characters of each word as they are split from the input string. We add 1 every time a word score is tested as a triangle number.

sum(is_tn(score(x[1:-1])) for x in open('words.txt').read().split(','))

HackerRank version

This solution easily solves HackerRank Project Euler 42 which requires us to test 100,000 numbers up to 1018 for being a triangular number. If it is we print its triangle index or print -1 when it’s not. So, 2 would print -1 and 55 would print 10.

from math import sqrt
for _ in range(input()):
	tr = (sqrt(1 + 8*input()) - 1) / 2
	print -1 if tr % 1 else int(tr)

Python 2.7 Source

Last Word