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?

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.NOTE:

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 9*99 times with 10 letters => 9*99*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 🙂

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”

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

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”)

HI Lyle

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

/Kristian

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.

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

/Kristian

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.

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 ????

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.

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)

i have writtten code in vb. i am getting answer 21148. whats wrong in my code

Dim length As UInt32 = 11

Private Sub Form1_Load(sender As Object, e As EventArgs) Handles MyBase.Load

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

[…] http://www.mathblog.dk/project-euler-17-letters-in-the-numbers-1-1000/ […]

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.Threading.Tasks;

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);

Console.ReadKey();

}

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;

}

}

}

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.

Hello,

I just wanted to point out a typo “We have “hundred and” occurring 999 times with 10 letters => 999

10 = 8910″10 = 8910. Overall, this was a really nice write up.This should be 891

Thanks!

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. => 7

9 = 6310 = 8910″ are wrong.2. We have “hundred and” occurring 999 times with 10 letters => 999

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. => 36

100 = 3600854 = 76862. 1-99 occurring 9 times => 9

3. The word “hundred” appearing 900 times => 7

900 = 6300891 = 26734. The word “and” appearing 891 times => 3

So in total we have

3600 + 7686 + 6300 + 2673 = 20259

Thanks and God bless 🙂

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.

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()

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

10 = 891099 as 999.”“I think you misread the 9

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= 7481 > 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

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

10 = 891099 as 999.”“I think you misread the 9

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= 7481 > 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

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]))

1010]sum = sum + dic[a] + dic[int(str(i)[0])

dic[i] = dic[a] + dic[int(str(i)[0])

10]100elif i > 100 and i <1000:

b = i – (int(str(i)[0]))

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)

Hey, your artle may have a little problem,

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

10 = 8910 ”10 = 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