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

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.