Project Euler Problem 42

Solution

Answer: 162

The key task is to determine how many words in the supplied file have a word value equal to a triangle number.

A triangle number is defined by

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

The first few are:

$$1,3,6,10,15,21,28,36,45,55,\dots$$

For example:

• $S=19$
• $K=11$
• $Y=25$

so

$$19+11+25 = 55$$

and since

$$55 = \frac{10\cdot 11}{2}$$

SKY is a triangle word.

---

Step 1 — Mathematical Analysis

Converting a word into a number

Each letter maps to its alphabetical index:

$$A=1,;B=2,;\dots,;Z=26$$

If a word has letters $c_1,c_2,\dots,c_k$, its value is

$$V = \sum_{i=1}^{k} \text{value}(c_i)$$

Example:

$$\text{SKY}=19+11+25=55$$

---

Determining whether a number is triangular

We need to know whether some integer $x$ satisfies

$$x=\frac{n(n+1)}2$$

Rearrange:

$$n^2+n-2x=0$$

Using the quadratic formula:

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

So $x$ is triangular exactly when

$$1+8x$$

is a perfect square and the resulting $n$ is an integer.

---

Maximum possible word value

The words file contains common English words; the maximum word length is small. Even if a word had 20 letters all equal to Z:

$$20\cdot 26 = 520$$

So only a modest set of triangle numbers is needed.

A practical approach:

1. Read all words
2. Compute each word value
3. Precompute all triangle numbers up to the maximum value
4. Count matches

This is efficient because lookup in a set is $O(1)$.

---

Step 2 — Python Implementation

from math import sqrt

# Read the words file
with open("0042_words.txt") as f:
    content = f.read()

# The file format is:
# "WORD1","WORD2","WORD3",...
words = [w.strip('"') for w in content.split(",")]

# Function to compute word value
def word_value(word):
    return sum(ord(c) - ord('A') + 1 for c in word)

# Compute all word values
values = [word_value(w) for w in words]

# Find the largest value
max_value = max(values)

# Generate all triangle numbers up to max_value
triangle_numbers = set()

n = 1
while True:
    t = n * (n + 1) // 2
    if t > max_value:
        break
    triangle_numbers.add(t)
    n += 1

# Count triangle words
count = sum(1 for v in values if v in triangle_numbers)

print(count)

---

Step 3 — Code Walkthrough

Reading the file

with open("0042_words.txt") as f:
    content = f.read()

Loads the entire file into memory.

---

Splitting into words

words = [w.strip('"') for w in content.split(",")]

The file stores words like:

"SKY","HELLO","WORLD"

We split on commas and remove quotation marks.

---

Computing word values

def word_value(word):
    return sum(ord(c) - ord('A') + 1 for c in word)

ord('A') gives ASCII code 65.

So:

• A → $65-65+1=1$
• B → $66-65+1=2$
• …
• Z → 26

Example:

word_value("SKY")

gives

$$19+11+25=55$$

which matches the problem statement.

---

Generating triangle numbers

t = n * (n + 1) // 2

This implements

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

We stop once the triangle number exceeds the largest word value.

Using a set allows very fast membership testing.

---

Counting triangle words

count = sum(1 for v in values if v in triangle_numbers)

For every word value:

• add 1 if triangular
• add 0 otherwise

---

Step 4 — Final Verification

Known examples:

• SKY → 55
• $55=t_{10}$

The algorithm correctly identifies this.

The total number of words is about 2000, and triangle numbers below the maximum word value are few, so the computation is tiny and exact.

Running the code on the official Project Euler word list gives:

$$162$$

---

Answer: 162