Project Euler 17: Letters in the numbers 1-1000

Written by on 25 December 2010

Topics: Project Euler

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

12 Comments For This Post I'd Love to Hear Yours!

  1. Alex says:

    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”

  2. Kristian says:

    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

  3. Lyle says:

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

  4. Kristian says:

    HI Lyle

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

    /Kristian

  5. peterparker says:

    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.

  6. Kristian says:

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

    /Kristian

  7. reiden4 says:

    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.

  8. Sumanth says:

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

  9. Kristian says:

    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.

  10. Jean-Marie Hachey says:

    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)

  11. Rahul says:

    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

  12. Carlos says:

    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;

    }
    }
    }

Trackbacks For This Post

  1. Problem 17: Number letter counts | loctv

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

This site uses cookies.