Problem 42: Coded Triangle Numbers

Mathematical Development

Definitions

Definition 1. The alphabetical value of a letter $c \in \{\text{A}, \ldots, \text{Z}\}$ is $\operatorname{pos}(c) = \operatorname{ord}(c) - \operatorname{ord}(\text{A}) + 1 \in \{1, 2, \ldots, 26\}$.

Definition 2. The word value of a word $w = c_1 c_2 \cdots c_L$ is $V(w) = \sum_{i=1}^{L} \operatorname{pos}(c_i)$.

Definition 3. A positive integer $v$ is a triangular number if $v = T_n = \frac{n(n+1)}{2}$ for some $n \in \mathbb{Z}^+$.

Theoretical Development

Theorem 1 (Triangular number characterization). A positive integer $v$ is triangular if and only if $8v + 1$ is a perfect square.

Proof. ($\Rightarrow$) Suppose $v = \frac{n(n+1)}{2}$ for some $n \in \mathbb{Z}^+$. Then

which is a perfect square.

($\Leftarrow$) Suppose $8v + 1 = m^2$ for some $m \in \mathbb{Z}^+$. Since $8v + 1 \equiv 1 \pmod{8}$ and even squares satisfy $m^2 \equiv 0$ or $4 \pmod{8}$, we conclude $m$ is odd. Write $m = 2n + 1$ for some $n \in \mathbb{Z}_{\geq 0}$. Then

Since $v \geq 1$, we have $n \geq 1$, confirming $v$ is triangular. $\square$

Corollary 1 (Constant-time test). The triangular number test requires $O(1)$ arithmetic operations: compute $\Delta = 8v + 1$, take the integer square root $s = \lfloor \sqrt{\Delta} \rfloor$, and verify $s^2 = \Delta$.

Proof. Immediate from Theorem 1. The integer square root and one multiplication-comparison suffice. $\square$

Lemma 1 (Word value bounds). For a non-empty word of length $L$, the word value satisfies $L \leq V(w) \leq 26L$.

Proof. Each letter contributes at least $\operatorname{pos}(\text{A}) = 1$ and at most $\operatorname{pos}(\text{Z}) = 26$. Summing over $L$ letters gives $L \leq V(w) \leq 26L$. $\square$

Remark. For the Project Euler word list, the maximum word length is $14$ (e.g., “SIMULTANEOUSLY”), giving $V(w) \leq 26 \cdot 14 = 364$. The largest triangle number not exceeding $364$ is $T_{26} = 351$, so we need only consider triangle numbers $T_1, T_2, \ldots, T_{26}$.

Editorial

We read the word list, compute the value of each word by summing the alphabetical positions of its letters, and test the resulting integer with the triangular-number criterion from Theorem 1. Every word whose value satisfies that criterion contributes one to the running count, and the final count is the number of triangle words in the file.

Pseudocode

Algorithm: Counting Triangle Words
Require: A finite word list over the alphabet {A, B, ..., Z}.
Ensure: The number of words whose alphabetical values are triangular numbers.
1: Read the word list and initialize count ← 0.
2: For each word w in the list, compute its word value v ← sum of the letter positions in w.
3: Test whether 8v + 1 is a perfect square.
4: If the test succeeds, increment count.
5: Return count.

Complexity Analysis

Proposition (Time complexity). The algorithm runs in $O(W \cdot \bar{L})$ time, where $W$ is the number of words and $\bar{L}$ is the average word length.

Proof. For each of the $W$ words, computing the word value requires summing $L_i$ letter values, where $L_i$ is the length of the $i$-th word. The triangular number test is $O(1)$ by Corollary 1. Total time:

$\square$

Proposition (Space complexity). The algorithm uses $O(W \cdot \bar{L})$ space for storing the word list, plus $O(1)$ auxiliary space.

Answer

#include <bits/stdc++.h>
using namespace std;

bool is_triangular(int v) {
    // v is triangular iff 8v+1 is a perfect square (Theorem 1).
    if (v <= 0) return v == 0;
    long long disc = 1 + 8LL * v;
    long long s = (long long)sqrt((double)disc);
    while (s * s < disc) s++;
    while (s * s > disc) s--;
    return s * s == disc;
}

int word_value(const string& w) {
    int val = 0;
    for (char c : w) {
        if (c >= 'A' && c <= 'Z') val += c - 'A' + 1;
    }
    return val;
}

int main() {
    vector<string> candidates = {
        "words.txt",
        "0042_words.txt",
        "project_euler/problem_042/words.txt",
        "project_euler/problem_042/0042_words.txt"
    };

    ifstream fin;
    for (const auto& path : candidates) {
        fin.open(path);
        if (fin.is_open()) {
            break;
        }
        fin.clear();
    }

    if (!fin.is_open()) {
        cerr << "Could not locate the Problem 42 word list." << endl;
        return 1;
    }

    string line;
    getline(fin, line);
    fin.close();

    int count = 0;
    stringstream ss(line);
    string token;
    while (getline(ss, token, ',')) {
        string word;
        for (char c : token) {
            if (c != '"') word += c;
        }
        if (is_triangular(word_value(word))) {
            count++;
        }
    }

    cout << count << endl;
    return 0;
}

import math
from pathlib import Path


def is_triangular(v):
    """Check if v is a triangular number using the discriminant criterion:
    v = n(n+1)/2 iff 8v+1 is a perfect square.
    """
    if v <= 0:
        return v == 0
    disc = 1 + 8 * v
    s = math.isqrt(disc)
    return s * s == disc


def word_value(word):
    """Compute the alphabetical value of a word: A=1, B=2, ..., Z=26."""
    return sum(ord(c) - ord('A') + 1 for c in word.upper())


def load_words():
    script_dir = Path(__file__).resolve().parent
    candidates = [
        script_dir / "words.txt",
        script_dir / "0042_words.txt",
        Path("words.txt"),
        Path("0042_words.txt"),
        Path("project_euler/problem_042/words.txt"),
        Path("project_euler/problem_042/0042_words.txt"),
    ]

    for path in candidates:
        if path.exists():
            return path.read_text().strip()

    raise FileNotFoundError("Could not locate the Problem 42 word list.")


def solve():
    content = load_words()
    words = [w.strip('"') for w in content.split(',')]
    return sum(1 for w in words if is_triangular(word_value(w)))


answer = solve()
assert answer == 162
print(answer)