Project Euler Page 2

Project Euler - Page 1

Problem 13

Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.
37107287533902102798797998220837590246510135740250
46376937677490009712648124896970078050417018260538
and so on. Navigate to Problem 13 at ProjectEuler.net to see the full list. The first thing I did was copy and paste the values into Notepad and save a txt file.
Then I wrote a short VBA program to read the 100 values in to a worksheet, column A. In column B I entered the worksheet function

= Len(A2)

to make sure I had read in all 50 digits of each value. Here's the read in program


	            

	            Sub Problem13ReadData()
                

    Dim lngCounter As Long

    Dim strLine As String

    

    On Error GoTo Problem13ReadData_Err

    

    lngCounter = 2

    

    Open "C:\Users\Geoff\Documents\ProjectEuler\Solved\Problem13.txt" For Input As #1

    

    Do While Not EOF(1)

        Input #1, strLine

        Range("A" & lngCounter).NumberFormat = "@"

        Range("A" & lngCounter).Value = strLine

        lngCounter = lngCounter + 1

    Loop

    

    Close #1

    

Problem13ReadData_Exit:

    Exit Sub

    

Problem13ReadData_Err:

    MsgBox prompt:=Err.Number & " " & Err.Description

    Close #1

    Resume Problem13ReadData_Exit

End Sub

The error trapping may seem unnecessary, but if you do encounter a runtime error while reading the file without error trapping, the Close statement will not run. Then when you fix the problem that caused the runtime error, and rerun the procdure, another error will occur because filenumber 1 is still open.

Since an Excel worksheet couldn't handle such large numbers simply by a worksheet function such as

=A1+A2+A3

I wrote a VBA program to add the 50 values. The key technique was to add up the numbers the way you would if you were doing this on paper. Take the first two numbers. Working from right to left, 0 + 8 = 8, 5 + 3 = 8, 2 + 5 = 7, 0 + 0 = 0, 4 + 6 = 10. Here you store the 0 in a string, 0788, and store the carry over value 1 separately, to be added to the next sum (7 + 2) + 1. When you're done, store the result 83484225211392112511446123117807668296927154000788 in cell C2. This is a useful technique for testing the procedure. In the 2nd iteration, add the 3rd 50 digit value 74324986199524741059474233309513058123726617309629 in cell A4 to the value in cell C2. Store the reult in cell C3 and so on.
Here is the program that does the iterations and storing:


	            Sub StartProblem13()



    Dim lngCounter As Long

    Dim strCurrent1 As String

    Dim strCurrent2 As String

    

    Debug.Print Timer

    strCurrent1 = Range("A2").Value

    strCurrent2 = Range("A3").Value

    

    Range("C3").NumberFormat = "@"

    Range("C3").Value = Problem13(strCurrent1:=strCurrent1, strCurrent2:=strCurrent2)

    

    For lngCounter = 4 To 101

        strCurrent1 = Range("C" & lngCounter - 1).Value 'This is the cumulative total.

        strCurrent2 = Range("A" & lngCounter).Value 'This is one of the 50 original values.

        Range("C" & lngCounter).NumberFormat = "@"

        Range("C" & lngCounter).Value = Problem13(strCurrent1:=strCurrent1, strCurrent2:=strCurrent2)

    Next lngCounter

    Debug.Print Timer

End Sub

I'll leave it to the reader to figure out what the procedure Problem13 does exactly. It does the right to left addition.

Problem 14

The following iterative sequence is defined for the set of positive integers:

n n/2 (n is even)
n 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 40 20 10 5 16 8 4 2 1
It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

This was a pretty short VBA procedure. Basically you need to
count from 2 to 999,999
Do While the term is positive
If the term is even use the even calculation else use the odd calculation. Count the terms. Loop
Once the loop finishes, see if the number of terms was greater than the number of terms in the last iteration (from 2 to 999,999). This took 31 sconds.

Problem 16

2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.
What is the sum of the digits of the number 2^1000? (2 to the 100th power)

I used the same technique as I did in Problem 13. Since Excel cells could not handle a figure such as 2^100, I wrote a procedure that stored the value in a string, "128" (=2^7) for example and then digit-by-digit, working from right to left as you would on paper, I calculated 2 x "128" = "652". The reverse of this is "256" = 2^8. The only thing you have to watch out for is a calculation such as 2 x 6 = 12. You need to store the "2" in the resultant string, and carry over the "1" to the next calculation. The procedure took less than a second to run.

Problem 17

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.

In column A of a worksheet, I entered 1 in cell A1, 2 in cell A2 selected cells A1 and A2 and used the fill down symbol that was in the lower right hand corner of cell A2 to generate the sequence 1 ... 1000. Then I wrote a procedure to write out the words of the numbers in column A.
First I bult two arrays.


            aNums(1) = "one"

            aNums(2) = "two"

            aNums(3) = "three"

            'etc

            aTens(2) = "twenty"

            aTens(3) = "thirty"

            aTens(4) = "forty"

            'etc

Then I looped down column A. Determine the length of the number. If it's 1, then simply write out the appropriate aNums() value in column B. If the length is 2, values 10 to 19 were straightforward. For values 20 to 99, you have to test if the last digit is a 0 or not. If it is, then write out the appropriate aTens() value. If it is not a zero then you have to concatenate the appropriate aTens() and aNums() values. I added the hyphen to make sure I was doing it right, then did a replace

strNum = Replace(strNum, "-", "", 1, -1, vbTextCompare)

at the end. Remember to use the Replace function to remove spaces. For 3 digit numbers such as 203, it's a case of separating the 2, concatenating "hundred", and building the words the same way you would for a 2 digit number. Once the word has been built "twohundredandthree", calculate it's length in column C. The procedure took less than a second to run.

Problem 18

I solved problem 18 in a worksheet using the Max worksheet formula. I replicated the triangle in a worksheet and reduce it's size by one row with the Max formula. Then I copied the smaller triangle and repeated the technique.

Problem 19

How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?
This was straightforward.
Loop while the year is < 2001.
Build a date string such as "2/1/1901"
Use the Weekday function to see if it is equal to vbSunday.
If it is, increment the counter.

Problem 42

How many triangle words does the list of common English words contain? I solved this one in sections. First, I read in the file of 1786 words into column A of a worksheet.


	            Sub ReadWords()


    Dim intCount As Long

    Dim intCounter As Long

    Dim lngRowCounter As Long

    Dim strLine As String

    Dim strList() As String

    
    Open "C:\Users\Documents\ProjectEuler\words.txt" For Input As #1

    
    lngRowCounter = 1

    
    Do While Not EOF(1)

        Input #1, strLine

        strList = Split(strLine, " ", -1)

        intCount = UBound(strList)

        For intCounter = 0 To intCount

            Range("A" & lngRowCounter).Value = strList(intCounter)

            lngRowCounter = lngRowCounter + 1

        Next intCounter

    Loop

    Close #1

End Sub

Then I wrote a function to convert the 26 letters of the alphabet into their corresponding number.


	            Function LetterToNumber(strLetter As String) As Long

    Select Case strLetter

        Case "A"

            LetterToNumber = 1

        Case "B"

            LetterToNumber = 2

        Case "Z"

            LetterToNumber = 26

        Case Else

            LetterToNumber = 0

    End Select

End Function

I put the length of each word in column B and looked for the word with the maximum length so I could get an idea of how large a number the biggest word value would be. It turns out that RESPONSIBILTY had the largest word value of 192, which wasn't very big at all. In the end this was an unneccesary step. I wrote a procedure to create the value of each word. I put the value in column C.


	            Sub CreateWordValue()

    
    Dim lngCounter As Long

    Dim lngWordLen As Long

    Dim lngWordValue As Long

    Dim lngTriangleWordCount As Long

    Dim rng As Range

    Dim rngA As Range

    Dim strLetter As String

    Dim strWord As String

    
    Set rngA = Range("A2:A1787")

    lngTriangleWordCount = 0

    
    For Each rng In rngA

        strWord = rng.Value

        lngWordLen = Len(strWord)

        lngWordValue = 0

        For lngCounter = 1 To lngWordLen

            strLetter = Mid(strWord, lngCounter, 1)

            lngWordValue = lngWordValue + LetterToNumber(strLetter:=strLetter)

        Next lngCounter

        rng.Offset(0, 2).Value = lngWordValue

    Next rng

    
End Sub

I filled down in column F values from 1 to 19. In column G I entered the triangle number formula =0.5*F3*(F3+1) and filled down. The 19th triangle number is 190, just less than the word value for RESPONSIBILTY. I did a Vlookup in column D to see if the word values in column C were in the list of triangle numbers in column G =VLOOKUP(C2,$G$3:$G$21,1,FALSE) and filled down column D. Finally, I entered a CountIf function at the end of column D to get the count of triangle words I wanted =COUNTIF(D2:D1787,">0").