# Project Euler 17: Letters in the numbers 1-1000

Problem 17 of Project Euler changes character completely compared to the previous exercises. The problem reads

If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.

If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?

NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of “and” when writing out numbers is in compliance with British usage.

If we just wanted to write them out and count them, it would take a long time. So we will have to make some pattern analysis. I have solved in without using a computer, but I am fairly sure you can turn the analysis into a general algorithm.

## Numbers 1-9

There is no particular pattern in the first numbers, so all we can do is spell them out and count them.

3 + 3 + 5 +4 + 4 +3 +5 +5 +4 = 36

## Numbers 10-19

There is also too little pattern in the next 10 numbers that I want to make a deal out of it, so if we count those as well we get

3 + 6 + 6 + 8 + 8 + 7 + 7 + 9 + 8 + 8 = 70

## Numbers 20-99

Now a pattern starts emerging. For each period of ten numbers, we have a prefix 10 times and then the sequence 1-9, which we have already counted.  So we need to figure out how many letters the tens contain and add 8*36.

10*(6 + 6 + 5 + 5 + 5 + 7 + 6 + 6) + 8*36 = 748

So if we sum that up the number 1-99 will contain 36 + 70 + 74 8= 854 letters

## Numbers 100-999

We will use sort of the same trick here.

If we look at one hundred and twenty two (122) and  four hundred and fifty three (453). We will see that the number 1-9 is prepended, then comes the words “hundred and” (10 letters), and last comes a number between 1 and 99.  Whole hundreds such as two hundred (200) are a special case where you have the numbers 1-9 followed by “hundred” (7 letters).

If we break it down we have the numbers 1-9 occurring 100 times each. => 36*100 = 3600

1-99 occurring 9 times => 9*854 = 7686

We have “hundred” occurring 9 times with 7 letters. => 7*9 = 63

We have “hundred and” occurring 999 times with 10 letters => 999*10 = 8910

So in total we have

3600 + 7686 + 63 + 8910= 20259

## Summing up

We still miss one thousand which is another 11 letters, so in total we have 854 + 20259 + 11 = 21124 letters in the numbers 1-1000

I have seen people who code it using the same analysis such as Samuel Jack over at Functional Fun, but I think I will stop it here.

And before signing off. For those of you who celebrate Christmas, I hope you have a happy. To you who does not, I just hope you have a pleasant day with lots of good spirit 🙂

### Posted by Kristian

I was trying to solve this the combinatorics way too, but my answer was off for some reason but this helped fix my logic. The brute force way — everyone seems to be doing — seemed like an undue burden and too much typing!

Found a couple of typos:

In the 20-99 section

“36 + 70 + 74 = 8854” should be “36+70+748=854”

Kristian

Hi Alex
I am glad it fixed your logic. As I remember it, I had to recount it several times to get it right. Also thanks for noticing the typo. It is fixed now.

/Kristian

Lyle

Thank you! This helped me identify where the problem in my code was. I discovered that my 1-99 calculation was 10 characters over which led me to the discovery that I spelled “forty” incorrectly. It’s times like this I hate English (one would expect it to be spelled “fourty”)

Kristian

HI Lyle

Yes it is wonderful isn’t it. Especially since fourteen is spelled with a u.

/Kristian

peterparker

I have written a python code using your logic to solve this problem. I don’t know how to post the code in readabale format. Your method is a great hack which one can think to cut the time.

Kristian

Either post it in tags [ python ] [ /python ] without the spaces in the tags, or you can post it on pastebin.

/Kristian

reiden4

what a great and simple solution.. I got it right but it took me a while by using strings and adding its length.. I have never thought of this solution and after I saw this I was like. did I just waste an hour when it could have been this simple lol.

Sumanth

hey Kristian,
i was wondering why do we count 1-99 9 times where it occurs 10 times in 1-1000.
001
101
201
301
401
501
601
701
801
901
1 a part of 1-99 occurs 10 times but why did you count it 9 times ????

Kristian

Sorry for the long reply time.
The reason is that I counted the 1-99 seperatly since I use it as a building block for counting in the hundreds.

Jean-Marie Hachey

Table 1
Letters in the numbers 1-1000
Re: [Project Euler – Problem 17]
Number letter counts

http://img11.hostingpics.net/pics/907988pe17tab1nbrct.jpg

Results in Table 1 were obtained using algo in ref. (1).

___

Sources:
1) Project Euler in C#
http://siralansdailyramble.blogspot.ca/2009/04/project-euler-17.html
2) Number to Text Converter
http://www.calculator.org/calculate-online/mathematics/text-number.aspx
3) Microsoft Visual C# 2010 Express
4) Microsoft Office Excel (2007)

Rahul

i have writtten code in vb. i am getting answer 21148. whats wrong in my code
Dim length As UInt32 = 11
For i = 1 To 999
If i / 10 1 And i / 10 = 2 And i / 10 = 11 And i Mod 100 <= 19 Then
length += 10
single_digit(Math.Floor(i / 100))
ele_twe_thi(i Mod 100)
ElseIf i Mod 100 = 10 Then
length += 3
single_digit(Math.Floor(i / 100))
length += 10
Else
length += 10
single_digit(Math.Floor(i / 100))
multiple_10(Math.Floor((i Mod 100) / 10) * 10)
single_digit(i Mod 10)
End If
Next
MsgBox(length)
End Sub
Private Sub single_digit(num)
If num = 1 Then
length = length + 3
ElseIf num = 2 Then
length = length + 3
ElseIf num = 3 Then
length = length + 5
ElseIf num = 4 Then
length = length + 4
ElseIf num = 5 Then
length = length + 4
ElseIf num = 6 Then
length = length + 3
ElseIf num = 7 Then
length = length + 5
ElseIf num = 8 Then
length = length + 5
ElseIf num = 9 Then
length = length + 4
End If
End Sub
Private Sub ele_twe_thi(num)
If num = 11 Or num = 12 Then
length = length + 6
ElseIf num = 13 Or num = 14 Or num = 18 Or num = 19 Then
length = length + 8
ElseIf num = 17 Then
length = length + 9
ElseIf num = 15 Or num = 16 Then
length = length + 7
End If
End Sub
Private Sub multiple_10(num)
If num = 20 Then
length = length + 6
ElseIf num = 30 Then
length = length + 6
ElseIf num = 40 Then
length = length + 5
ElseIf num = 50 Then
length = length + 5
ElseIf num = 60 Then
length = length + 5
ElseIf num = 70 Then
length = length + 7
ElseIf num = 80 Then
length = length + 6
ElseIf num = 90 Then
length = length + 6
End If
End Sub
Private Sub ten()
length = length + 3
End Sub

Carlos

Hi.
I’ve written a code in c# to count the letters that took (in the best run) 2 ms.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace Euler_17
{
class Program
{
static void Main(string[] args)
{
Stopwatch clock = Stopwatch.StartNew();

int numberOfLetters = 0;

for (int number = 1; number < 1001; number++)
numberOfLetters += CountLetters(number);

clock.Stop();
Console.WriteLine("Number of letters: " + numberOfLetters);
Console.WriteLine("Answer reached in {0} ms.", clock.ElapsedMilliseconds);

}

static int CountLetters (int number)
{
string[] units = new string[] { "", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine" };
string[] units10 = new string[] { "", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen" };
string[] tens = new string[] {"", "ten", "twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety" };

if (number == 1000)
return "onethousand".Length;
string numberString = "";
int[] digits = new int[3];

digits[0] = number / 100;
digits[1] = (number / 10) % 10;
digits[2] = number % 10;

if (digits[0] > 0)
{
numberString += units[digits[0]] + "hundred";
if (digits[1] != 0 || digits[2] != 0)
numberString += "and";
}

if (digits[1] == 1)
{
if (digits[2] == 0)
numberString += tens[digits[1]];
else
numberString += units10[digits[2]];
}
else
numberString += tens[digits[1]] + units[digits[2]];

return numberString.Length;

}
}
}

dumetrulo

Brute-force F# version:

http://ideone.com/MblTZI

Not as sophisticated as Samuel Jack’s version, since I only needed to convert numbers up to 1000.

Aaron

Hello,

I just wanted to point out a typo “We have “hundred and” occurring 999 times with 10 letters => 99910 = 8910″
This should be 891
10 = 8910. Overall, this was a really nice write up.

Thanks!

Ethan

Hi Kristian,

Firstly thank you for spending time to write this elaborate explanation. It really helps people to identify the logic behind this problem.

However I believe that the following two logical statements
“1. We have “hundred” occurring 9 times with 7 letters. => 79 = 63
2. We have “hundred and” occurring 999 times with 10 letters => 999
10 = 8910″ are wrong.
This is because there are only 1000 numbers from 1-1000, and stating that “hundred and” occurs 999 times means that only 1 number did not have the letters “hundred and”, but there is more than one number which did not have the letters “hundred and”, such as “one”, “two”, “three”… and so on. Furthermore, if we combine statements 1 and 2, “hundred” would have appeared a total of 1008 times, which obviously exceeds the number range, and hence not right either.

The answer your logic produces may be correct, but in fact the right logic for 100-999 should be:
1. If we break it down we have the numbers 1-9 occurring 100 times each. => 36100 = 3600
2. 1-99 occurring 9 times => 9
854 = 7686
3. The word “hundred” appearing 900 times => 7900 = 6300
4. The word “and” appearing 891 times => 3
891 = 2673
So in total we have
3600 + 7686 + 6300 + 2673 = 20259

Thanks and God bless 🙂

Kristian

Hi Ethan

Thanks for the comment. Re-reading my own statements I state that “hundred” occurs 9 times, and “hundred and” occurs 9*99 = 891 times, for a total of 900 times. If we then add 1-99 and thousand it sums to thousand numbers. I do believe that is correct.

I think you misread the 9*99 as 999.

saqib ahmed

var hun = [“”,””,””,”hundred”, “thousand”];
var digit = [“zero”,”one”,”two”,”three”,”four”,”five”,”six”,”seven”,”eight”,”nine”];
var tn = [‘eleven’,’twelve’,’thirteen’, ‘fourteen’,’fifteen’,’sixteen’, ‘seventeen’,’eighteen’,’nineteen’]
var tens = [“ten”,”twenty”,”thirty”,”fourty”,”fifty”,”sixty”,”seventy”,”eighty”,”ninety”];

function countLetterFromNumber(n){
var x = n.toString().split(“”).length;
var numbers = n.toString().split(“”)
var stringNumber = “”
if(x == 1 ){
stringNumber = digit[n];
return stringNumber
}
else if(x == 2 && n <= 20){
stringNumber = numbers[1] == 0 ? tens[numbers[0]-1] : tn[numbers[1]-1]
return stringNumber
}
else if(x == 2 && n > 20){
stringNumber = tens[numbers[0]-1] + ” ” + (numbers[1] == 0 ? “” : digit[numbers[1]])
return stringNumber.replace(/\s/g, ”);
}
else if(x==3){
var isHundred = numbers[1] == 0 && numbers[2] == 0 ? true : false
if(isHundred){
stringNumber = digit[numbers[0]] +” “+ hun[x]
return stringNumber.replace(/\s/g, ”);
}
stringNumber = digit[numbers[0]] +” “+ hun[x] + ” and “+ (numbers[1] == 0 && numbers[2] > 0 ? digit[numbers[2]] : numbers[1] > 0 && numbers[2] == 0 ? tens[numbers[1]-1] : numbers[1] == 1 && numbers[2] > 0 ? tn[numbers[2]-1] : numbers[1] == 1 && numbers[2] >= 0 ? tens[numbers[2]] : numbers[1] > 1 && numbers[2] > 1 ? tens[numbers[1]-1]+ “” + digit[numbers[2]] : “”)
return stringNumber.replace(/\s/g, ”);
}
else if(x == 4){
if(n == 1000){
return “onethousand”;
}
var noIncludeDigit1 = numbers[2] == 1 || numbers[2] == 0 ? true : false
stringNumber = digit[numbers[0]] +” “+ hun[x] + digit[numbers[1]]+” “+ hun[3] +” and “+ (numbers[2] == 0 ? “” : numbers[2] < 2 ? tn[numbers[3]-1] : tens[numbers[2]-2]) + “” + (numbers[2] == 1 || numbers[2] == 0 || numbers[3] == 0 ? “” : digit[numbers[3]])
return stringNumber.replace(/\s/g, ”);
}
}

var totalLetter = 0
var n = 1000
for(var i=1;i<=n;i++){
var letter = countLetterFromNumber(i)
totalLetter += letter.length
}
debug(totalLetter)
// debug(countLetterFromNumber(30))

Thanks again Kristian for a nice write up! I see you are still very active on this blog responding in the year 2018 !! I used python but feels it is too slow, timed out as 0.14s. Definitely way much slower than an optimal solution. I feel append is adding to the overall time.

from num2words import num2words
import time

def main():
start=time.time()
n=[]
for i in range(1,1001):
n.append((num2words(i)))
str1=”.join(n)
str1=str1.replace(‘ ‘,”)
str1=str1.replace(‘-‘,”)
print len(str1)
end=time.time()
print end-start

main()

Băliban

We have “hundred and” occurring 999 times with 10 letters => 99910 = 8910
“I think you misread the 9
99 as 999.”
it realy write 999 cant misread that its snot 9*99

so explaining w no words:
1=3 one
2=3 two
3=5 three
4=4 four
5=4 five
6=3 six
7=5 seven
8=5 eight
9=4 nine
============3 + 3 + 5 +4 + 4 +3 +5 +5 +4 =36
10=3 ten
11=6 eleven
12=6 twelve
13=8 thirteen
14=8 fourteen
15=7 fifteen
16=7 sixteen
17=9 seventeen
18=8 eighteen
19=8 nineteen
============3 + 6 + 6 + 8 + 8 + 7 + 7 + 9 + 8 + 8 = 70
20=6 twenty
30=6 thirty
40=5 forty
50=5 fifty
60=5 sixty
70=7 seventy
80=6 eighty
90=6 ninety

============(6 + 6 + 5 + 5 + 5 + 7 + 6 + 6)10 + 368 = 4610 + 368= 748

1 > 9=36 36 x10 = 360
10>19=70 70 x10 = 700
20>99=748 748 x10 = 7480
=854 854 x10 = 8540 +

x00=houndred = 7 >> 7 x 9 =63 + +x=1 to 9;=>36×1
x00=houndred and =10>>99*9=10x 891=8910 + +x=1 to 9;=>36×99 => 3600 +
1000=one thousand =11 +

8540 + 63 + 8910 + 3600 + 11 = 21124

Vernian

We have “hundred and” occurring 999 times with 10 letters => 99910 = 8910
“I think you misread the 9
99 as 999.”
u realy write 999 cant misread that its not 9*99

so explaining w no words:
1=3 one
2=3 two
3=5 three
4=4 four
5=4 five
6=3 six
7=5 seven
8=5 eight
9=4 nine
============3 + 3 + 5 +4 + 4 +3 +5 +5 +4 =36
10=3 ten
11=6 eleven
12=6 twelve
13=8 thirteen
14=8 fourteen
15=7 fifteen
16=7 sixteen
17=9 seventeen
18=8 eighteen
19=8 nineteen
============3 + 6 + 6 + 8 + 8 + 7 + 7 + 9 + 8 + 8 = 70
20=6 twenty
30=6 thirty
40=5 forty
50=5 fifty
60=5 sixty
70=7 seventy
80=6 eighty
90=6 ninety

============(6 + 6 + 5 + 5 + 5 + 7 + 6 + 6)10 + 368 = 4610 + 368= 748

1 > 9=36 36 x10 = 360
10>19=70 70 x10 = 700
20>99=748 748 x10 = 7480
=854 854 x10 = 8540 +

x00=houndred = 7 >> 7 x 9 =63 + +x=1 to 9;=>36×1
x00=houndred and =10>>99*9=10x 891=8910 + +x=1 to 9;=>36×99 => 3600 +
1000=one thousand =11 +

8540 + 63 + 8910 + 3600 + 11 = 21124

after ive seen this page made my thinking upside down ….i dont find what is writen organised its like a mambo jambo for me

naman

hi kristian!!!
can you tell me , why this python code is giving 21145 instead of 21124….

sum = 0
dic = {0:0,1:3,2:3,3:5,4:4,5:4,6:3,7:5,8:5,9:4,10:3,11:6,12:6,13:8,14:8,15:7,16:7,17:9,18:8,19:8,20:6,30:6,40:5,50:5,60:5,70:7,80:6,90:6,100:7}
for i in range(1,1001):
if i <= 20:
sum = sum + dic[i]
elif i > 20 and i < 100:
a = i – (int(str(i)[0]))10
sum = sum + dic[a] + dic[int(str(i)[0])
10]
dic[i] = dic[a] + dic[int(str(i)[0])10]
elif i > 100 and i <1000:
b = i – (int(str(i)[0]))
100
sum = sum + dic[int(str(i)[0])] + 10 + dic[b]
dic[i] = dic[int(str(i)[0])] + 10 + dic[b]
elif i == 100:
sum = sum + dic[100]
else:
sum = sum + 11
print(sum)

fangyun

Hey, your artle may have a little problem,
” We have “hundred and” occurring 999 times with 10 letters => 99910 = 8910 ”
I think maybe you don’t write right, it should be ” We have “hundred and” occurring (900-9 = 891) times with 10 letters => 891
10 = 8910 “