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

15 comments

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.

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)

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.

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!

Leave a Reply