Problem 17 asks for the total number of letters used when the integers from 1 to 1000 are written out in British English words, with spaces and hyphens ignored. For example, three hundred and forty-two contributes 23 letters, and one hundred and fifteen contributes 20.
The key point is that this is not a string-processing problem in disguise. Once the English naming rules are fixed, every number from 1 to 1000 falls into a small number of arithmetic cases: units, teens, tens with an optional unit, hundreds with an optional remainder, and the special case 1000. The implementations exploit exactly that structure.
Let \(L(n)\) be the number of letters in the British English name of \(n\), after removing spaces and hyphens. The solution is built from three tiny lookup tables and one recursive reduction from a number in \(100\) to \(999\) down to its remainder modulo \(100\).
The implementations use the following fixed letter counts:
$$u(0),u(1),\dots,u(9)=(0,3,3,5,4,4,3,5,5,4),$$
$$v(0),v(1),\dots,v(9)=(3,6,6,8,8,7,7,9,8,8),$$
$$t(0),t(1),\dots,t(9)=(0,0,6,6,5,5,5,7,6,6).$$
Here \(u(d)\) counts the words one through nine, \(v(r)\) counts ten through nineteen via \(10+r\), and \(t(q)\) counts the decade words twenty through ninety. The constants \(7\) and \(3\) come from the words hundred and and.
With those objects, \(L(n)\) is completely described by the piecewise rule
$$L(n)=\begin{cases} u(n), & 1\le n\le 9,\\ v(n-10), & 10\le n\le 19,\\ t(\lfloor n/10\rfloor)+u(n\bmod 10), & 20\le n\le 99,\\ u(h)+7, & n=100h,\ 1\le h\le 9,\\ u(h)+7+3+L(r), & n=100h+r,\ 1\le h\le 9,\ 1\le r\le 99,\\ 11, & n=1000. \end{cases}$$
The invariant behind the last two lines is simple: after stripping off the hundreds prefix, every non-round hundred leaves a remainder \(r\in\{1,\dots,99\}\), and the counting problem becomes exactly the same subproblem as before, just on a smaller number.
The first useful block is the range \(1\) to \(99\). Define
$$U=\sum_{d=1}^{9}u(d)=36,\qquad V=\sum_{r=0}^{9}v(r)=70.$$
For each decade \(20q\) to \(20q+9\) with \(q\in\{2,\dots,9\}\), the decade word appears ten times and the unit words \(1\) through \(9\) appear once each. Therefore
$$\sum_{n=10q}^{10q+9}L(n)=10\,t(q)+U.$$
Adding the unit block, the teen block, and the eight decade blocks gives
$$B=\sum_{n=1}^{99}L(n)=U+V+\sum_{q=2}^{9}\bigl(10\,t(q)+U\bigr)=854.$$
This constant \(B\) is the backbone of the whole count, because every nontrivial hundreds block contains one copy of the entire \(1\) to \(99\) pattern.
Fix a hundreds digit \(h\in\{1,\dots,9\}\). The block from \(100h\) to \(100h+99\) contains:
$$100\bigl(u(h)+7\bigr)$$
letters from the prefix \(h\) hundred, because that prefix appears in all 100 numbers of the block. Among those 100 numbers, exactly 99 are not multiples of 100, so British usage inserts and exactly 99 times, contributing
$$99\cdot 3.$$
The remainders \(1\) through \(99\) also appear once each, so the rest of the contribution is another copy of \(B\). Hence the entire block sum is
$$H_h=\sum_{n=100h}^{100h+99}L(n)=100\bigl(u(h)+7\bigr)+99\cdot 3+B.$$
Now sum the initial block \(1\) to \(99\) together with the nine hundreds blocks:
$$\sum_{n=1}^{999}L(n)=B+\sum_{h=1}^{9}H_h=10B+100\sum_{h=1}^{9}\bigl(u(h)+7\bigr)+9\cdot 99\cdot 3=21113.$$
Finally, \(1000\) contributes one thousand, which has \(11\) letters, so
$$\sum_{n=1}^{1000}L(n)=21113+11=21124.$$
The two checkpoint values used by the implementations illustrate the rule cleanly. For \(342\), we write \(342=300+42\), so
$$L(342)=L(3)+7+3+L(42)=5+7+3+(5+3)=23.$$
For \(115\), the remainder lies in the teen range:
$$L(115)=L(1)+7+3+L(15)=3+7+3+7=20.$$
These examples show why the British and matters: omitting it would make both counts too small.
The C++, Python, and Java implementations never build the English words themselves. They store only the three constant tables above, plus the two fixed additions for hundred and and. That turns the problem from text handling into pure integer arithmetic.
For a single number, the implementation first handles \(1000\) as a special case. Otherwise it checks whether the number has a hundreds digit; if so, it adds the hundreds prefix, reduces the number modulo \(100\), and adds \(3\) more letters exactly when the remainder is nonzero. The remaining value is then dispatched to one of three cases: \(20\) to \(99\), \(10\) to \(19\), or \(0\) to \(9\).
After that, the total answer is just the sum of this per-number routine over the desired interval. The Project Euler target is \(1\) through \(1000\), while the C++ implementation also exposes smaller limits between \(1\) and \(1000\). The implementations include checkpoint examples such as \(1\) through \(5\mapsto 19\), \(342\mapsto 23\), and \(115\mapsto 20\), all of which follow directly from the piecewise formula above.
The implementations perform constant work for each integer in the range, so the running time is \(O(N)\) for a limit \(N\le 1000\). Since every lookup table has fixed size and only a few integer variables are used, the extra space usage is \(O(1)\).
Mathematically, the derivation above also yields an \(O(1)\) closed-form evaluation for the specific target \(N=1000\). The implementations choose the simpler loop because at this scale it is already instantaneous and mirrors the English-number rules very directly.
In Problem 17 soll die Gesamtzahl der Buchstaben bestimmt werden, die beim Ausschreiben der Zahlen von 1 bis 1000 im britischen Englisch auftreten, wobei Leerzeichen und Bindestriche nicht mitgezählt werden. Zum Beispiel hat three hundred and forty-two 23 Buchstaben und one hundred and fifteen 20.
Entscheidend ist, dass das Problem keine eigentliche Zeichenkettenverarbeitung verlangt. Sobald die englischen Benennungsregeln feststehen, zerfällt jede Zahl von 1 bis 1000 in wenige arithmetische Fälle: Einer, Teens, Zehner mit optionalem Einer, Hunderter mit optionalem Rest und der Spezialfall 1000. Genau diese Struktur nutzen die Implementierungen aus.
Sei \(L(n)\) die Anzahl der Buchstaben im britisch-englischen Zahlwort von \(n\), nachdem Leerzeichen und Bindestriche entfernt wurden. Die gesamte Lösung basiert auf drei kleinen Nachschlagetabellen und einer Reduktion, die Zahlen zwischen \(100\) und \(999\) auf ihren Rest modulo \(100\) zurückführt.
Die Implementierungen verwenden die festen Werte
$$u(0),u(1),\dots,u(9)=(0,3,3,5,4,4,3,5,5,4),$$
$$v(0),v(1),\dots,v(9)=(3,6,6,8,8,7,7,9,8,8),$$
$$t(0),t(1),\dots,t(9)=(0,0,6,6,5,5,5,7,6,6).$$
Dabei steht \(u(d)\) für die Wörter eins bis neun, \(v(r)\) für zehn bis neunzehn über \(10+r\), und \(t(q)\) für die Zehnerwörter zwanzig bis neunzig. Die Konstanten \(7\) und \(3\) sind die Längen von hundred und and.
Damit ist \(L(n)\) vollständig durch die Fallunterscheidung
$$L(n)=\begin{cases} u(n), & 1\le n\le 9,\\ v(n-10), & 10\le n\le 19,\\ t(\lfloor n/10\rfloor)+u(n\bmod 10), & 20\le n\le 99,\\ u(h)+7, & n=100h,\ 1\le h\le 9,\\ u(h)+7+3+L(r), & n=100h+r,\ 1\le h\le 9,\ 1\le r\le 99,\\ 11, & n=1000. \end{cases}$$
Die Invariante der letzten beiden Zeilen lautet: Sobald der Hunderterpräfix abgezogen ist, bleibt bei jeder nichtglatten Hunderterzahl ein Rest \(r\in\{1,\dots,99\}\), und genau dasselbe Teilproblem tritt erneut auf.
Der erste wichtige Block ist der Bereich \(1\) bis \(99\). Definiere
$$U=\sum_{d=1}^{9}u(d)=36,\qquad V=\sum_{r=0}^{9}v(r)=70.$$
Für jedes Zehnerintervall \(10q\) bis \(10q+9\) mit \(q\in\{2,\dots,9\}\) erscheint das Zehnerwort zehnmal, und die Einerwörter \(1\) bis \(9\) erscheinen jeweils einmal. Daher gilt
$$\sum_{n=10q}^{10q+9}L(n)=10\,t(q)+U.$$
Zusammen mit dem Einerblock und dem Teen-Block ergibt das
$$B=\sum_{n=1}^{99}L(n)=U+V+\sum_{q=2}^{9}\bigl(10\,t(q)+U\bigr)=854.$$
Diese Konstante \(B\) ist zentral, weil jeder Hunderterblock mit Rest genau eine vollständige Kopie des Musters von \(1\) bis \(99\) enthält.
Fixiere eine Hunderterziffer \(h\in\{1,\dots,9\}\). Im Block von \(100h\) bis \(100h+99\) liefert der Präfix \(h\) hundred den Beitrag
$$100\bigl(u(h)+7\bigr),$$
weil er in allen 100 Zahlen des Blocks vorkommt. Unter diesen 100 Zahlen sind genau 99 keine Vielfachen von 100, also erscheint das britische and genau 99-mal und trägt
$$99\cdot 3$$
bei. Außerdem treten die Reste \(1\) bis \(99\) je einmal auf, also kommt nochmals \(B\) hinzu. Damit ist
$$H_h=\sum_{n=100h}^{100h+99}L(n)=100\bigl(u(h)+7\bigr)+99\cdot 3+B.$$
Nun addieren wir den Anfangsblock \(1\) bis \(99\) und die neun Hunderterblöcke:
$$\sum_{n=1}^{999}L(n)=B+\sum_{h=1}^{9}H_h=10B+100\sum_{h=1}^{9}\bigl(u(h)+7\bigr)+9\cdot 99\cdot 3=21113.$$
Für \(1000\) kommt noch one thousand mit 11 Buchstaben hinzu, also
$$\sum_{n=1}^{1000}L(n)=21113+11=21124.$$
Die in den Implementierungen verwendeten Kontrollwerte zeigen die Regel sehr klar. Für \(342\) gilt \(342=300+42\), also
$$L(342)=L(3)+7+3+L(42)=5+7+3+(5+3)=23.$$
Für \(115\) liegt der Rest im Teen-Bereich:
$$L(115)=L(1)+7+3+L(15)=3+7+3+7=20.$$
Gerade diese Beispiele zeigen, warum das britische and unverzichtbar ist. Lässt man es weg, wird das Ergebnis sofort zu klein.
Die Implementierungen in C++, Python und Java erzeugen die englischen Wörter nie als Zeichenketten. Gespeichert werden nur die drei konstanten Tabellen sowie die festen Zuschläge für hundred und and. Das macht aus einem Sprachproblem eine reine Ganzzahlrechnung.
Für eine einzelne Zahl wird zuerst \(1000\) als Spezialfall behandelt. Andernfalls prüft die Implementierung, ob eine Hunderterziffer vorhanden ist; falls ja, wird der Hunderterpräfix addiert, die Zahl modulo \(100\) reduziert und genau dann ein weiterer Zuschlag von \(3\) addiert, wenn der Rest ungleich null ist. Anschließend wird der Rest in einen der drei Fälle \(20\) bis \(99\), \(10\) bis \(19\) oder \(0\) bis \(9\) eingeordnet.
Danach ist die Gesamtlösung nur noch die Summe dieser Einzelroutine über das ganze Intervall. Das Project-Euler-Ziel ist der Bereich \(1\) bis \(1000\); die C++-Version erlaubt zusätzlich kleinere Grenzen zwischen \(1\) und \(1000\). Kontrollwerte wie \(1\) bis \(5\mapsto 19\), \(342\mapsto 23\) und \(115\mapsto 20\) folgen direkt aus der obigen Fallunterscheidung.
Die Implementierungen leisten für jede Zahl im Bereich konstanten Aufwand. Für eine Grenze \(N\le 1000\) beträgt die Laufzeit also \(O(N)\). Die drei Tabellen haben feste Größe, und zusätzlich werden nur wenige Ganzzahlvariablen benötigt; der Speicherverbrauch ist daher \(O(1)\).
Die mathematische Herleitung liefert für das konkrete Ziel \(N=1000\) sogar eine geschlossene \(O(1)\)-Auswertung. Die Implementierungen bleiben dennoch bei der einfachen Schleife, weil sie auf dieser Größenordnung sofort fertig ist und die Regelstruktur der englischen Zahlwörter unmittelbar widerspiegelt.
Problem 17, 1 ile 1000 arasındaki tüm sayıların İngiliz İngilizcesiyle yazıldığında kullandığı toplam harf sayısını ister; boşluklar ve kısa çizgiler sayılmaz. Örneğin three hundred and forty-two 23 harf, one hundred and fifteen ise 20 harf verir.
Buradaki asıl nokta, bunun gerçekte bir dize üretme problemi olmamasıdır. İngilizce sayı adlandırma kuralları sabitlendiğinde, 1 ile 1000 arasındaki her sayı birkaç aritmetik sınıfa düşer: birler, teen grubu, isteğe bağlı birler basamağı taşıyan onlar, isteğe bağlı kalanı olan yüzler ve özel durum olan 1000. Uygulamalar tam olarak bu yapıyı kullanır.
\(L(n)\), \(n\) sayısının İngiliz İngilizcesindeki yazımında kullanılan harf sayısı olsun; boşluklar ve kısa çizgiler çıkarılmış kabul edilir. Çözüm, üç küçük tablo ve \(100\) ile \(999\) arasındaki bir sayıyı \(100\) modundaki kalana indirgeyen tek bir kuralla kuruluyor.
Uygulamalarda kullanılan sabit sayımlar şunlardır:
$$u(0),u(1),\dots,u(9)=(0,3,3,5,4,4,3,5,5,4),$$
$$v(0),v(1),\dots,v(9)=(3,6,6,8,8,7,7,9,8,8),$$
$$t(0),t(1),\dots,t(9)=(0,0,6,6,5,5,5,7,6,6).$$
Burada \(u(d)\) birden dokuza kadar olan kelimeleri, \(v(r)\) sayıları \(10+r\) biçiminde düşünerek on ile on dokuz arasını, \(t(q)\) ise yirmiden dokuza kadar onlar kelimelerini sayar. \(7\) ve \(3\) sabitleri de sırasıyla hundred ve and kelimelerinin uzunluklarıdır.
Böylece \(L(n)\) şu parça parça tanımla tamamen belirlenir:
$$L(n)=\begin{cases} u(n), & 1\le n\le 9,\\ v(n-10), & 10\le n\le 19,\\ t(\lfloor n/10\rfloor)+u(n\bmod 10), & 20\le n\le 99,\\ u(h)+7, & n=100h,\ 1\le h\le 9,\\ u(h)+7+3+L(r), & n=100h+r,\ 1\le h\le 9,\ 1\le r\le 99,\\ 11, & n=1000. \end{cases}$$
Son iki satırdaki temel değişmez şudur: yüzler öneki çıkarıldıktan sonra, 100'ün tam katı olmayan her sayıda kalan \(r\in\{1,\dots,99\}\) olur ve problem aynen daha küçük bir sayı için tekrar ortaya çıkar.
İlk önemli blok \(1\) ile \(99\) arasıdır. Şu toplamları tanımlayalım:
$$U=\sum_{d=1}^{9}u(d)=36,\qquad V=\sum_{r=0}^{9}v(r)=70.$$
\(q\in\{2,\dots,9\}\) için \(10q\) ile \(10q+9\) arasındaki her onluk blokta onlar kelimesi on kez görünür; birler kelimeleri \(1\) ile \(9\) arasında birer kez eklenir. Bu yüzden
$$\sum_{n=10q}^{10q+9}L(n)=10\,t(q)+U$$
olur. Birler bloğu, teen bloğu ve sekiz onluk bloğu birlikte toplandığında
$$B=\sum_{n=1}^{99}L(n)=U+V+\sum_{q=2}^{9}\bigl(10\,t(q)+U\bigr)=854.$$
Bu \(B\) sabiti çözümün omurgasıdır; çünkü yüzler bloklarının her biri, yüzler önekinin arkasında tam bir \(1\) ile \(99\) deseni taşır.
Sabit bir yüzler basamağı \(h\in\{1,\dots,9\}\) seçelim. \(100h\) ile \(100h+99\) arasındaki blokta \(h\) hundred öneki bütün 100 sayıda bulunduğu için toplam katkısı
$$100\bigl(u(h)+7\bigr)$$
olur. Bu 100 sayının tam 99 tanesi 100'ün tam katı değildir; dolayısıyla Britanya yazımındaki and tam 99 kez gelir ve
$$99\cdot 3$$
harf ekler. Geriye kalan kısım da 1'den 99'a kadar kalanların birer kez görünmesidir; yani bir tane daha \(B\) gelir. Böylece tüm blok toplamı
$$H_h=\sum_{n=100h}^{100h+99}L(n)=100\bigl(u(h)+7\bigr)+99\cdot 3+B$$
şeklindedir. Başlangıçtaki \(1\) ile \(99\) bloğunu ve dokuz yüzler bloğunu toplayınca
$$\sum_{n=1}^{999}L(n)=B+\sum_{h=1}^{9}H_h=10B+100\sum_{h=1}^{9}\bigl(u(h)+7\bigr)+9\cdot 99\cdot 3=21113$$
elde edilir. Son olarak \(1000\), yani one thousand, 11 harf verdiğinden
$$\sum_{n=1}^{1000}L(n)=21113+11=21124.$$
Uygulamalardaki kontrol örnekleri kuralı doğrudan gösterir. \(342=300+42\) olduğundan
$$L(342)=L(3)+7+3+L(42)=5+7+3+(5+3)=23.$$
\(115\) için kalan teen aralığına düşer:
$$L(115)=L(1)+7+3+L(15)=3+7+3+7=20.$$
Bu iki örnek, Britanya İngilizcesindeki and kullanımının neden zorunlu olduğunu açıkça gösterir. Onu kaldırırsanız sonuç hemen küçülür.
C++, Python ve Java uygulamaları İngilizce sayı kelimelerini hiç üretmez. Yalnızca yukarıdaki üç sabit tabloyu ve hundred ile and için iki sabit eklemeyi tutar. Böylece problem metin işlemek yerine doğrudan tamsayı aritmetiğine indirgenir.
Tek bir sayı için önce \(1000\) özel durum olarak ele alınır. Aksi halde uygulama yüzler basamağı olup olmadığına bakar; varsa yüzler öneki eklenir, sayı \(100\) moduna indirilir ve kalan sıfır değilse tam o zaman 3 harflik and eklenir. Kalan parça daha sonra \(20\) ile \(99\), \(10\) ile \(19\) ya da \(0\) ile \(9\) durumlarından birine gönderilir.
Bundan sonra toplam cevap, bu tek-sayı rutinini istenen aralıkta toplamak olur. Project Euler hedefi \(1\) ile \(1000\) arasıdır; C++ sürümü ayrıca \(1\) ile \(1000\) arasındaki daha küçük üst sınırları da kabul eder. \(1\) ile \(5\mapsto 19\), \(342\mapsto 23\) ve \(115\mapsto 20\) gibi denetimler doğrudan yukarıdaki formülden çıkar.
Uygulamalar aralıktaki her sayı için sabit sayıda işlem yapar. Dolayısıyla üst sınır \(N\le 1000\) iken çalışma süresi \(O(N)\) olur. Tabloların boyutu sabittir ve yalnızca birkaç tamsayı değişkeni kullanılır; ek bellek tüketimi \(O(1)\)'dir.
Yukarıdaki matematiksel çözüm, özel hedef \(N=1000\) için kapalı biçimde \(O(1)\) hesap da verir. Buna rağmen uygulamalar daha sade olan döngülü yolu seçer; çünkü bu ölçekte zaten anlıktır ve İngilizce sayı yazım kurallarını doğrudan yansıtır.
El problema 17 pide contar cuántas letras se usan al escribir los enteros del 1 al 1000 en inglés británico, ignorando espacios y guiones. Por ejemplo, three hundred and forty-two aporta 23 letras y one hundred and fifteen aporta 20.
La observación importante es que no hace falta construir cadenas. Una vez fijadas las reglas de escritura en inglés, cada número entre 1 y 1000 cae en unos pocos casos aritméticos: unidades, números del 10 al 19, decenas con una unidad opcional, centenas con un resto opcional y el caso especial 1000. Las implementaciones trabajan exactamente con esa descomposición.
Sea \(L(n)\) el número de letras del nombre inglés británico de \(n\), después de eliminar espacios y guiones. Toda la solución se apoya en tres tablas diminutas y en una reducción que lleva cualquier número de \(100\) a \(999\) a su resto módulo \(100\).
Las implementaciones usan los conteos fijos
$$u(0),u(1),\dots,u(9)=(0,3,3,5,4,4,3,5,5,4),$$
$$v(0),v(1),\dots,v(9)=(3,6,6,8,8,7,7,9,8,8),$$
$$t(0),t(1),\dots,t(9)=(0,0,6,6,5,5,5,7,6,6).$$
Aquí \(u(d)\) cuenta one a nine, \(v(r)\) cuenta ten a nineteen por medio de \(10+r\), y \(t(q)\) cuenta las palabras de las decenas desde twenty hasta ninety. Las constantes \(7\) y \(3\) provienen de hundred y and.
Con eso, la función queda descrita por
$$L(n)=\begin{cases} u(n), & 1\le n\le 9,\\ v(n-10), & 10\le n\le 19,\\ t(\lfloor n/10\rfloor)+u(n\bmod 10), & 20\le n\le 99,\\ u(h)+7, & n=100h,\ 1\le h\le 9,\\ u(h)+7+3+L(r), & n=100h+r,\ 1\le h\le 9,\ 1\le r\le 99,\\ 11, & n=1000. \end{cases}$$
La invariante de las dos últimas líneas es que, una vez retirada la parte de las centenas, cualquier número no múltiplo exacto de 100 deja un resto \(r\in\{1,\dots,99\}\), y ese resto se resuelve con exactamente la misma lógica que ya usamos debajo de 100.
El primer bloque importante es \(1\) a \(99\). Definimos
$$U=\sum_{d=1}^{9}u(d)=36,\qquad V=\sum_{r=0}^{9}v(r)=70.$$
Para cada bloque \(10q\) a \(10q+9\) con \(q\in\{2,\dots,9\}\), la palabra de las decenas aparece diez veces y las unidades \(1\) a \(9\) aparecen una vez cada una. Por tanto,
$$\sum_{n=10q}^{10q+9}L(n)=10\,t(q)+U.$$
Sumando el bloque de unidades, el bloque 10 a 19 y los ocho bloques de decenas, obtenemos
$$B=\sum_{n=1}^{99}L(n)=U+V+\sum_{q=2}^{9}\bigl(10\,t(q)+U\bigr)=854.$$
Esta constante \(B\) es fundamental porque cada bloque de centenas con resto contiene una copia completa del patrón de \(1\) a \(99\).
Fijemos una cifra de centenas \(h\in\{1,\dots,9\}\). En el bloque de \(100h\) a \(100h+99\), el prefijo \(h\) hundred aparece en los 100 números, de modo que aporta
$$100\bigl(u(h)+7\bigr).$$
Dentro de ese bloque, exactamente 99 números no son múltiplos exactos de 100, así que la partícula británica and aparece 99 veces y contribuye
$$99\cdot 3.$$
Además, los restos \(1\) a \(99\) aparecen una vez cada uno, aportando otro \(B\). Por ello, el total del bloque es
$$H_h=\sum_{n=100h}^{100h+99}L(n)=100\bigl(u(h)+7\bigr)+99\cdot 3+B.$$
Ahora sumamos el bloque inicial \(1\) a \(99\) y los nueve bloques de centenas:
$$\sum_{n=1}^{999}L(n)=B+\sum_{h=1}^{9}H_h=10B+100\sum_{h=1}^{9}\bigl(u(h)+7\bigr)+9\cdot 99\cdot 3=21113.$$
Finalmente, \(1000\) añade one thousand, que tiene 11 letras, y por tanto
$$\sum_{n=1}^{1000}L(n)=21113+11=21124.$$
Los ejemplos de control usados por las implementaciones muestran la regla con claridad. Como \(342=300+42\), tenemos
$$L(342)=L(3)+7+3+L(42)=5+7+3+(5+3)=23.$$
Para \(115\), el resto cae en el intervalo de 10 a 19:
$$L(115)=L(1)+7+3+L(15)=3+7+3+7=20.$$
Ambos ejemplos dejan claro por qué el and británico es esencial. Si se omite, el conteo queda corto.
Las implementaciones en C++, Python y Java no generan las palabras inglesas. Guardan únicamente las tres tablas constantes y los dos incrementos fijos asociados a hundred y and. Así el problema se convierte en aritmética entera pura.
Para un número individual, la implementación trata primero \(1000\) como caso especial. En otro caso, comprueba si hay una cifra de centenas; si la hay, suma el prefijo de centenas, reduce el número módulo \(100\) y añade otras \(3\) letras exactamente cuando el resto es no nulo. El valor restante se clasifica después en uno de tres casos: \(20\) a \(99\), \(10\) a \(19\) o \(0\) a \(9\).
Una vez definida esa rutina, la respuesta total es simplemente la suma sobre el intervalo deseado. El objetivo de Project Euler es \(1\) a \(1000\), mientras que la implementación en C++ también admite límites menores entre \(1\) y \(1000\). Comprobaciones como \(1\) a \(5\mapsto 19\), \(342\mapsto 23\) y \(115\mapsto 20\) salen directamente de la fórmula por casos.
Las implementaciones hacen trabajo constante por cada número del intervalo, así que para un límite \(N\le 1000\) el tiempo es \(O(N)\). Las tablas tienen tamaño fijo y solo se usan unas pocas variables enteras, de modo que el espacio adicional es \(O(1)\).
La derivación matemática también da una evaluación cerrada \(O(1)\) para el caso concreto \(N=1000\). Aun así, el código usa el bucle sencillo porque a esta escala es inmediato y refleja de forma directa las reglas de los numerales ingleses.
第 17 题要求统计把 1 到 1000 的所有整数用英式英语写出来时，一共会用到多少个字母；空格和连字符都不计入。比如 three hundred and forty-two 共有 23 个字母，one hundred and fifteen 共有 20 个字母。
这个问题的关键并不是字符串拼接，而是把英文数字词的结构转成一个小而稳定的计数规则。只要英式英语的写法固定下来，1 到 1000 之间的每个整数都会落入有限的几类：个位数、10 到 19、带可选个位的整十数、带可选余数的整百数，以及特例 1000。三个实现都严格按照这套结构计数。
记 \(L(n)\) 为整数 \(n\) 的英式英语写法在去掉空格和连字符之后的字母数。整个解法建立在三个很小的查表数组之上，再配合一个核心递降规律：任何 \(100\) 到 \(999\) 之间的数，在处理掉百位前缀之后，都会变成一个 \(0\) 到 \(99\) 的余数问题。
实现中使用的固定计数是
$$u(0),u(1),\dots,u(9)=(0,3,3,5,4,4,3,5,5,4),$$
$$v(0),v(1),\dots,v(9)=(3,6,6,8,8,7,7,9,8,8),$$
$$t(0),t(1),\dots,t(9)=(0,0,6,6,5,5,5,7,6,6).$$
其中 \(u(d)\) 对应 one 到 nine，\(v(r)\) 通过 \(10+r\) 对应 ten 到 nineteen，\(t(q)\) 对应 twenty 到 ninety 这些整十词。常数 \(7\) 和 \(3\) 分别来自 hundred 和 and 的字母数。
于是 \(L(n)\) 可以完全写成下面这个分段函数：
$$L(n)=\begin{cases} u(n), & 1\le n\le 9,\\ v(n-10), & 10\le n\le 19,\\ t(\lfloor n/10\rfloor)+u(n\bmod 10), & 20\le n\le 99,\\ u(h)+7, & n=100h,\ 1\le h\le 9,\\ u(h)+7+3+L(r), & n=100h+r,\ 1\le h\le 9,\ 1\le r\le 99,\\ 11, & n=1000. \end{cases}$$
最后两行背后的不变量非常重要：如果 \(n\) 不是整百，那么把百位写出来以后，剩下的部分就是一个 \(1\) 到 \(99\) 之间的余数 \(r\)，而这个余数的字母数正好还是由同一套规则来决定。也就是说，整百以上并没有产生新类型，只是在原来 \(1\) 到 \(99\) 的问题外面多包了一层百位前缀与英式 and。
第一个关键常数是区间 \(1\) 到 \(99\) 的总字母数。设
$$U=\sum_{d=1}^{9}u(d)=36,\qquad V=\sum_{r=0}^{9}v(r)=70.$$
对于每个 \(q\in\{2,\dots,9\}\)，区间 \(10q\) 到 \(10q+9\) 的十位词会出现 10 次，而个位词 one 到 nine 各出现 1 次，因此
$$\sum_{n=10q}^{10q+9}L(n)=10\,t(q)+U.$$
这样把 \(1\) 到 \(9\)、\(10\) 到 \(19\) 以及八个整十区间全部加起来，得到
$$B=\sum_{n=1}^{99}L(n)=U+V+\sum_{q=2}^{9}\bigl(10\,t(q)+U\bigr)=854.$$
这个 \(B\) 是整道题的核心，因为每个非平凡的百位块后半部分，都完整地重现了一次 \(1\) 到 \(99\) 的结构。
固定一个百位数字 \(h\in\{1,\dots,9\}\)。在区间 \(100h\) 到 \(100h+99\) 中，前缀 \(h\) hundred 会在 100 个数里全部出现，因此它的总贡献是
$$100\bigl(u(h)+7\bigr).$$
在这 100 个数中，只有 \(100h\) 本身是整百，剩下 99 个数都需要在百位后插入英式的 and，因此又增加
$$99\cdot 3.$$
同时，余数 \(1\) 到 \(99\) 恰好各出现一次，所以还要再加一个 \(B\)。于是整个百位块的总和为
$$H_h=\sum_{n=100h}^{100h+99}L(n)=100\bigl(u(h)+7\bigr)+99\cdot 3+B.$$
把最前面的 \(1\) 到 \(99\) 和九个百位块一起加起来，就得到
$$\sum_{n=1}^{999}L(n)=B+\sum_{h=1}^{9}H_h=10B+100\sum_{h=1}^{9}\bigl(u(h)+7\bigr)+9\cdot 99\cdot 3=21113.$$
最后再把 \(1000\) 的 one thousand 算进去，它有 11 个字母，因此
$$\sum_{n=1}^{1000}L(n)=21113+11=21124.$$
实现中使用的检查值很适合说明公式。因为 \(342=300+42\)，所以
$$L(342)=L(3)+7+3+L(42)=5+7+3+(5+3)=23.$$
而 \(115\) 的余数落在 10 到 19 区间，所以
$$L(115)=L(1)+7+3+L(15)=3+7+3+7=20.$$
这两个例子都说明了同一件事：英式写法中的 and 不是装饰，而是总计数里必须保留的一部分。如果用美式省略法，答案会系统性偏小。
C++、Python 和 Java 实现都不会真的去拼接英文单词。它们只保存上面的三个常数表，以及 hundred 和 and 对应的两个固定增量。这样一来，整个问题就从“文字处理”变成了“按规则做整数加法”。
对某个具体的 \(n\)，实现先把 \(1000\) 单独处理。否则如果 \(n\ge 100\)，就先加上百位前缀，把 \(n\) 改写为 \(n\bmod 100\)，并且仅当这个余数非零时再补上 3 个字母的 and。随后对余数继续分类：若在 \(20\) 到 \(99\) 之间，就用整十表加个位表；若在 \(10\) 到 \(19\) 之间，就直接查 teen 表；否则就落回个位表。
总答案就是把这个单点计数过程对整个区间求和。Project Euler 题面要的是 \(1\) 到 \(1000\)；C++ 实现还额外支持 \(1\) 到 \(1000\) 之间的任意较小上界。像 \(1\) 到 \(5\mapsto 19\)、\(342\mapsto 23\)、\(115\mapsto 20\) 这样的检查值，正好验证了这套分段计数逻辑。
实现对区间中的每个整数都只做常数次查表和加法，因此若上界为 \(N\le 1000\)，时间复杂度就是 \(O(N)\)。所需额外空间只有三个固定长度的表和少量整数变量，所以空间复杂度为 \(O(1)\)。
从数学上说，上面的推导已经给出了 \(N=1000\) 时的闭式 \(O(1)\) 求值方式。代码仍然保留了线性遍历，是因为这个范围极小，循环同样瞬间完成，而且它与英文数字词的规则一一对应，读起来也更直接。
В задаче 17 требуется найти общее число букв, которые используются при записи всех целых чисел от 1 до 1000 словами на британском английском, если не учитывать пробелы и дефисы. Например, three hundred and forty-two дает 23 буквы, а one hundred and fifteen дает 20.
Это не задача о построении строк. Как только правила английских числительных зафиксированы, каждое число от 1 до 1000 попадает в один из немногих арифметических случаев: единицы, интервал от 10 до 19, десятки с необязательной единицей, сотни с необязательным остатком и особый случай 1000. Именно это разбиение и используют реализации.
Обозначим через \(L(n)\) число букв в британской английской записи числа \(n\) после удаления пробелов и дефисов. Вся конструкция решения опирается на три маленькие таблицы значений и на одно ключевое наблюдение: любое число от \(100\) до \(999\) после отделения сотенной части сводится к остатку по модулю \(100\).
Реализации используют такие фиксированные величины:
$$u(0),u(1),\dots,u(9)=(0,3,3,5,4,4,3,5,5,4),$$
$$v(0),v(1),\dots,v(9)=(3,6,6,8,8,7,7,9,8,8),$$
$$t(0),t(1),\dots,t(9)=(0,0,6,6,5,5,5,7,6,6).$$
Здесь \(u(d)\) описывает one до nine, \(v(r)\) описывает ten до nineteen через \(10+r\), а \(t(q)\) отвечает за слова десятков от twenty до ninety. Константы \(7\) и \(3\) — это длины слов hundred и and.
После этого функция \(L(n)\) полностью задается формулой
$$L(n)=\begin{cases} u(n), & 1\le n\le 9,\\ v(n-10), & 10\le n\le 19,\\ t(\lfloor n/10\rfloor)+u(n\bmod 10), & 20\le n\le 99,\\ u(h)+7, & n=100h,\ 1\le h\le 9,\\ u(h)+7+3+L(r), & n=100h+r,\ 1\le h\le 9,\ 1\le r\le 99,\\ 11, & n=1000. \end{cases}$$
Смысл двух последних строк таков: если число не является круглой сотней, то после записи сотенной части остается остаток \(r\in\{1,\dots,99\}\), и для него действует ровно та же схема подсчета, что и ниже 100. Это и есть основная инварианта задачи.
Первый важный блок — это числа от \(1\) до \(99\). Обозначим
$$U=\sum_{d=1}^{9}u(d)=36,\qquad V=\sum_{r=0}^{9}v(r)=70.$$
Для каждого \(q\in\{2,\dots,9\}\) на отрезке \(10q\) до \(10q+9\) слово десятка повторяется десять раз, а слова единиц one до nine добавляются по одному разу. Поэтому
$$\sum_{n=10q}^{10q+9}L(n)=10\,t(q)+U.$$
Если сложить блок единиц, блок от 10 до 19 и восемь блоков десятков, получится
$$B=\sum_{n=1}^{99}L(n)=U+V+\sum_{q=2}^{9}\bigl(10\,t(q)+U\bigr)=854.$$
Константа \(B\) важна потому, что каждый сотенный блок с ненулевыми остатками содержит одну полную копию структуры \(1\) до \(99\).
Зафиксируем цифру сотен \(h\in\{1,\dots,9\}\). В блоке от \(100h\) до \(100h+99\) префикс \(h\) hundred присутствует во всех 100 числах, поэтому он дает вклад
$$100\bigl(u(h)+7\bigr).$$
Среди этих 100 чисел ровно 99 не являются точными кратными 100, значит, британское and появляется ровно 99 раз и добавляет
$$99\cdot 3.$$
Кроме того, остатки \(1\) до \(99\) встречаются по одному разу, то есть добавляют еще один \(B\). Следовательно,
$$H_h=\sum_{n=100h}^{100h+99}L(n)=100\bigl(u(h)+7\bigr)+99\cdot 3+B.$$
Теперь складываем начальный блок \(1\) до \(99\) и девять сотенных блоков:
$$\sum_{n=1}^{999}L(n)=B+\sum_{h=1}^{9}H_h=10B+100\sum_{h=1}^{9}\bigl(u(h)+7\bigr)+9\cdot 99\cdot 3=21113.$$
После этого остается только число \(1000\), то есть one thousand, которое содержит 11 букв. Поэтому
$$\sum_{n=1}^{1000}L(n)=21113+11=21124.$$
Контрольные значения, используемые в реализациях, хорошо иллюстрируют правило. Поскольку \(342=300+42\), имеем
$$L(342)=L(3)+7+3+L(42)=5+7+3+(5+3)=23.$$
Для \(115\) остаток попадает в диапазон от 10 до 19:
$$L(115)=L(1)+7+3+L(15)=3+7+3+7=20.$$
Эти примеры показывают, что британское and нельзя опускать: без него результат систематически уменьшится.
Реализации на C++, Python и Java никогда не строят английские словесные записи явно. Они хранят только три постоянные таблицы и два фиксированных добавления для hundred и and. Благодаря этому задача сводится к чистой целочисленной арифметике.
Для отдельного числа сначала обрабатывается специальный случай \(1000\). Иначе код проверяет наличие сотенной цифры; если она есть, он добавляет сотенный префикс, заменяет число на остаток по модулю \(100\) и добавляет еще 3 буквы тогда и только тогда, когда остаток ненулевой. Затем остаток разбирается по одному из трех случаев: \(20\) до \(99\), \(10\) до \(19\) или \(0\) до \(9\).
После этого полный ответ получается простым суммированием этой процедуры по нужному диапазону. В задаче Project Euler нужен диапазон \(1\) до \(1000\), а реализация на C++ также позволяет использовать меньшие верхние границы от \(1\) до \(1000\). Проверки \(1\) до \(5\mapsto 19\), \(342\mapsto 23\) и \(115\mapsto 20\) непосредственно подтверждают корректность формулы.
На каждое число из диапазона приходится постоянное количество операций, поэтому при верхней границе \(N\le 1000\) время работы равно \(O(N)\). Поскольку таблицы имеют фиксированный размер и используются лишь несколько целочисленных переменных, дополнительная память составляет \(O(1)\).
С математической точки зрения вывод выше дает и закрытую \(O(1)\)-формулу для конкретного случая \(N=1000\). Однако реализации сохраняют линейный проход, потому что на таком малом диапазоне он мгновенный и очень прозрачно отражает сами правила английских числительных.
تطلب المسألة 17 حساب العدد الكلي للأحرف المستخدمة عند كتابة الأعداد الصحيحة من 1 إلى 1000 بالإنجليزية البريطانية، مع تجاهل المسافات والشرطات. فمثلًا العبارة three hundred and forty-two تحتوي 23 حرفًا، والعبارة one hundred and fifteen تحتوي 20 حرفًا.
الفكرة الأساسية هنا ليست إنشاء السلاسل النصية فعلًا، بل تحويل قواعد كتابة الأعداد بالإنجليزية إلى حالات حسابية صغيرة وثابتة. فكل عدد بين 1 و1000 ينتمي إلى واحدة من فئات قليلة: الآحاد، الأعداد من 10 إلى 19، العشرات مع آحاد اختيارية، المئات مع باقٍ اختياري، ثم الحالة الخاصة 1000. هذا بالضبط ما تستعمله التطبيقات.
لنرمز بـ \(L(n)\) إلى عدد أحرف الاسم الإنجليزي البريطاني للعدد \(n\) بعد حذف المسافات والشرطات. يعتمد الحل كله على ثلاثة جداول صغيرة جدًا، وعلى مبدأ اختزال واحد: أي عدد بين \(100\) و\(999\) يتحول بعد معالجة جزء المئات إلى مسألة على الباقي modulo \(100\).
تعتمد التطبيقات على القيم الثابتة التالية:
$$u(0),u(1),\dots,u(9)=(0,3,3,5,4,4,3,5,5,4),$$
$$v(0),v(1),\dots,v(9)=(3,6,6,8,8,7,7,9,8,8),$$
$$t(0),t(1),\dots,t(9)=(0,0,6,6,5,5,5,7,6,6).$$
حيث إن \(u(d)\) يمثل كلمات one إلى nine، و\(v(r)\) يمثل ten إلى nineteen عبر \(10+r\)، و\(t(q)\) يمثل كلمات العشرات من twenty إلى ninety. أما الثابتان \(7\) و\(3\) فهما طولا الكلمتين hundred وand.
وبذلك تُكتب الدالة \(L(n)\) كاملة بالصورة القطعية الآتية:
$$L(n)=\begin{cases} u(n), & 1\le n\le 9,\\ v(n-10), & 10\le n\le 19,\\ t(\lfloor n/10\rfloor)+u(n\bmod 10), & 20\le n\le 99,\\ u(h)+7, & n=100h,\ 1\le h\le 9,\\ u(h)+7+3+L(r), & n=100h+r,\ 1\le h\le 9,\ 1\le r\le 99,\\ 11, & n=1000. \end{cases}$$
اللافت في السطرين الأخيرين هو الثابت البنيوي للمسألة: بعد نزع بادئة المئات، فإن أي عدد ليس من مضاعفات 100 يترك باقيًا \(r\in\{1,\dots,99\}\)، وهذا الباقي لا يحتاج إلى منطق جديد، بل يُعالَج بالقواعد نفسها الخاصة بالأعداد الأصغر من 100.
أول ثابت مهم هو مجموع عدد الأحرف في المجال \(1\) إلى \(99\). نعرّف
$$U=\sum_{d=1}^{9}u(d)=36,\qquad V=\sum_{r=0}^{9}v(r)=70.$$
ولكل \(q\in\{2,\dots,9\}\)، فإن المجال من \(10q\) إلى \(10q+9\) يحتوي على كلمة العشرات نفسها عشر مرات، بينما تظهر كلمات الآحاد من 1 إلى 9 مرة واحدة لكل منها. لذا
$$\sum_{n=10q}^{10q+9}L(n)=10\,t(q)+U.$$
وبجمع مجال الآحاد، ومجال 10 إلى 19، وثمانية مجالات العشرات، نحصل على
$$B=\sum_{n=1}^{99}L(n)=U+V+\sum_{q=2}^{9}\bigl(10\,t(q)+U\bigr)=854.$$
هذا الثابت \(B\) هو قلب المسألة، لأن كل مجال مئات غير تافه يحتوي في جزئه الباقي نسخة كاملة من نمط الأعداد من 1 إلى 99.
لنثبت رقم مئات \(h\in\{1,\dots,9\}\). في المجال من \(100h\) إلى \(100h+99\)، تظهر البادئة \(h\) hundred في جميع الأعداد المئة، ولذلك تسهم بمقدار
$$100\bigl(u(h)+7\bigr).$$
ومن بين هذه الأعداد المئة، يوجد 99 عددًا ليس مضاعفًا تامًا لـ 100، ولذلك تظهر كلمة and البريطانية 99 مرة، فتضيف
$$99\cdot 3.$$
ثم إن البواقي من 1 إلى 99 تظهر مرة واحدة لكل منها، أي نضيف نسخة أخرى من \(B\). ومن ثم يكون مجموع الكتلة
$$H_h=\sum_{n=100h}^{100h+99}L(n)=100\bigl(u(h)+7\bigr)+99\cdot 3+B.$$
وبجمع الكتلة الأولى \(1\) إلى \(99\) مع كتل المئات التسع نحصل على
$$\sum_{n=1}^{999}L(n)=B+\sum_{h=1}^{9}H_h=10B+100\sum_{h=1}^{9}\bigl(u(h)+7\bigr)+9\cdot 99\cdot 3=21113.$$
وبعد ذلك نضيف \(1000\)، أي one thousand، وعدد أحرفه 11، فيصبح
$$\sum_{n=1}^{1000}L(n)=21113+11=21124.$$
قيم التحقق المستخدمة في التطبيقات توضّح القاعدة مباشرة. بما أن \(342=300+42\)، فإن
$$L(342)=L(3)+7+3+L(42)=5+7+3+(5+3)=23.$$
أما \(115\) فباقيه يقع في مجال 10 إلى 19، ومن ثم
$$L(115)=L(1)+7+3+L(15)=3+7+3+7=20.$$
ويُظهر هذان المثالان لماذا لا يمكن حذف and في الصياغة البريطانية: حذفها يؤدي مباشرة إلى عدٍّ أصغر من الصحيح.
التنفيذات في C++ وPython وJava لا تبني الكلمات الإنجليزية حرفيًا. إنها تحتفظ فقط بالجداول الثلاثة السابقة، وبالزيادتين الثابتتين الخاصتين بـ hundred وand. وبهذا تتحول المسألة إلى حسابات صحيحة بسيطة بدلًا من معالجة نصوص.
عند تقييم عدد مفرد، يبدأ التنفيذ بحالة \(1000\) الخاصة. وإلا فإنه يفحص ما إذا كان للعدد رقم مئات؛ فإن وجد، أضاف بادئة المئات، ثم استبدل العدد بباقيه modulo \(100\)، وأضاف 3 أحرف أخرى فقط عندما يكون الباقي غير صفري. بعد ذلك يُصنَّف الباقي في واحدة من ثلاث حالات: من \(20\) إلى \(99\)، أو من \(10\) إلى \(19\)، أو من \(0\) إلى \(9\).
وبعد تعريف هذه العملية لعدد واحد، يصبح الجواب الكلي مجرد مجموعها على المجال المطلوب. المطلوب في Project Euler هو \(1\) إلى \(1000\)، بينما يتيح تنفيذ C++ أيضًا حدودًا أصغر بين \(1\) و\(1000\). والتحققات من نوع \(1\) إلى \(5\mapsto 19\)، و\(342\mapsto 23\)، و\(115\mapsto 20\) تؤكد مباشرة صحة الصيغة القطعية السابقة.
تنفذ التطبيقات قدرًا ثابتًا من العمل لكل عدد في المجال، ولذلك يكون الزمن \(O(N)\) عندما يكون الحد الأعلى \(N\le 1000\). أما الذاكرة الإضافية فهي \(O(1)\)، لأن الجداول ثابتة الحجم ولا نحتاج إلا إلى عدد قليل من المتغيرات الصحيحة.
ومن الناحية الرياضية، فإن الاشتقاق السابق يعطي أيضًا طريقة مغلقة بزمن \(O(1)\) للحالة الخاصة \(N=1000\). لكن التنفيذات تبقي على المرور الخطي البسيط لأنه فوري تمامًا عند هذا الحجم، ولأنه يعكس قواعد الأعداد الإنجليزية بصورة مباشرة وواضحة.