Problem 17: Number Letter Counts

Mathematical Development

Definition 1 (Atomic letter counts). Define the following lookup tables:

Theorem 1 (Recursive decomposition of $\ell$). For $1 \le n \le 1000$:

where $[\cdot]$ denotes the Iverson bracket, the constant $7$ counts the letters in “hundred”, and $3$ counts those in “and”.

Proof. This follows directly from British English number-naming rules:

• Numbers 1—9 are single words with letter counts $o_k$.
• Numbers 10—19 (“ten” through “nineteen”) are single words with letter counts $t_k$.
• Numbers 20—99 are composed of a tens-word optionally followed by a ones-word.
• Numbers 100—999 have the form “[ones] hundred” optionally followed by “and [1—99]”.
• The number 1000 is “one thousand” with $3 + 8 = 11$ letters. $\square$

Lemma 1 (Sum over 1—9). $\Sigma_{1\text{--}9} = S_O = 36$.

Proof. $3 + 3 + 5 + 4 + 4 + 3 + 5 + 5 + 4 = 36$. $\square$

Lemma 2 (Sum over 10—19). $\Sigma_{10\text{--}19} = S_T = 70$.

Proof. $3 + 6 + 6 + 8 + 8 + 7 + 7 + 9 + 8 + 8 = 70$. $\square$

Lemma 3 (Sum over 20—99). $\Sigma_{20\text{--}99} = 10 \cdot S_D + 8 \cdot S_O = 748$.

Proof. Partition $\{20, \ldots, 99\}$ into eight decades $\{10j, \ldots, 10j+9\}$ for $j = 2, \ldots, 9$. In decade $j$, the tens-word $d_j$ appears in all 10 numbers, contributing $10 \cdot d_j$. The ones-words $o_1, \ldots, o_9$ appear once each (for the non-zero units digit), contributing $S_O$ per decade. Summing over all 8 decades:

Theorem 2 (Sum over 1—99).

Proof. Sum of Lemmas 1, 2, and 3. $\square$

Theorem 3 (Sum over a single hundred-block). For a hundreds digit $h \in \{1, \ldots, 9\}$, define $B_h = \{100h, 100h+1, \ldots, 100h+99\}$. Then

Proof. Each of the 100 numbers in $B_h$ begins with “[h] hundred”, contributing $o_h + 7$ letters per number. For the 99 numbers $100h + r$ with $1 \le r \le 99$, the word “and” (3 letters) and the representation of $r$ are appended. The remaining number $100h$ has no suffix. Therefore:

Theorem 4 (Total sum 1—1000).

Proof. Partition $\{1, \ldots, 1000\}$ into $\{1, \ldots, 99\}$, $B_1, B_2, \ldots, B_9$, and $\{1000\}$.

• $\Sigma_{1\text{--}99} = 854$ (Theorem 2).
• $\sum_{h=1}^{9}(100 \cdot o_h + 1851) = 100 \cdot S_O + 9 \cdot 1851 = 3600 + 16659 = 20259$ (Theorem 3).
• $\ell(1000) = 11$ (Theorem 1).

Total: $854 + 20259 + 11 = 21124$. $\square$

Editorial

We precompute the letter counts for the atomic words one through nineteen and the tens words twenty through ninety. A helper letterCount(n) decomposes each number according to British usage rules for hundreds and the word and, and the main loop sums that value for $n = 1$ to $N$. This is sufficient because every number in the range falls into one of the cases covered by the lookup-based decomposition.

Pseudocode

Algorithm: Letter Count for the Written Numbers from 1 to N
Require: An integer N with 1 ≤ N ≤ 1000.
Ensure: The total number of letters used when writing 1, 2, ..., N in words under British usage.
1: Prepare lookup tables for the atomic words up to nineteen, the tens words, and the fixed words "hundred", "and", and "thousand".
2: Initialize total ← 0.
3: For each n in {1, 2, ..., N}, decompose n into its thousands, hundreds, tens, and units parts and evaluate its British letter count from the lookup tables.
4: Update total ← total + letterCount(n).
5: Return total.

Complexity Analysis

Proposition 1. The algorithm runs in $\Theta(N)$ time and $\Theta(1)$ space.

Proof. The function $\ell(n)$ executes a fixed number of comparisons, lookups, and arithmetic operations, each in $O(1)$ time. The main loop calls $\ell$ exactly $N$ times. Storage is bounded by three constant-size lookup tables. $\square$

Answer

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

int letterCount(int n) {
    static const int ones[] = {0, 3, 3, 5, 4, 4, 3, 5, 5, 4};
    static const int teens[] = {3, 6, 6, 8, 8, 7, 7, 9, 8, 8};
    static const int tens[] = {0, 0, 6, 6, 5, 5, 5, 7, 6, 6};

    if (n == 1000) return 11;
    int c = 0;
    if (n >= 100) {
        c += ones[n / 100] + 7;
        n %= 100;
        if (n > 0) c += 3;
    }
    if (n >= 20) {
        c += tens[n / 10];
        n %= 10;
        c += ones[n];
    } else if (n >= 10) {
        c += teens[n - 10];
    } else {
        c += ones[n];
    }
    return c;
}

int main() {
    int total = 0;
    for (int i = 1; i <= 1000; i++)
        total += letterCount(i);
    cout << total << endl;
    return 0;
}

"""Project Euler Problem 17: Number Letter Counts"""

def letter_count(n):
    ones = [0, 3, 3, 5, 4, 4, 3, 5, 5, 4]
    teens = [3, 6, 6, 8, 8, 7, 7, 9, 8, 8]
    tens = [0, 0, 6, 6, 5, 5, 5, 7, 6, 6]
    if n == 1000:
        return 11
    c = 0
    if n >= 100:
        c += ones[n // 100] + 7
        n %= 100
        if n > 0:
            c += 3
    if n >= 20:
        c += tens[n // 10]
        n %= 10
    if 10 <= n <= 19:
        c += teens[n - 10]
        n = 0
    if 1 <= n <= 9:
        c += ones[n]
    return c

def main():
    print(sum(letter_count(n) for n in range(1, 1001)))