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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s