Project Euler problem 18

Source code available on GitHub.

  By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

  That is, \(3 + 7 + 4 + 9 = 23\).  Find the maximum total from top to bottom of the triangle below:

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

  \footnotesize \textbf{NOTE:} As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)

This is a really wonderful problem, another great example of dynamic programming.
(continued)

Read More

Project Euler problem 17

Source code available on GitHub.

  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?  \footnotesize \textbf{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.

This problem got me thinking about turning numerals into words, and I actually spent quite a while solving this problem much more fully than I had to. I’m not going to explain my full solution: that’s for a different post.

Suffice to say, I wrote a script that will print, in British English short-scale words, any integer from 0 to 10^{64} (10^{63} is one vigintillion, after which Wikipedia runs out of names). It took quite a lot of effort and made me realise just how subtle our numbering rules actually are. Here’s the code:

# D Falck.

(continued)

Read More

Project Euler problem 15

Source code available on GitHub.

  Starting in the top left corner of a \(2 \times 2\) grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

 


  How many such routes are there through a \(20 \times 20\) grid?

This looks confusing at first, and it’s easy to get lost combinatorially. However, this type of problem is a typical example of where we can use basic dynamic programming.

Dynamic programming is where, instead of trying to do the whole thing at once, you build up gradually piece by piece. In this case, we want to consider very carefully what it means to go from one corner to the next.

Say we label the vertical lines as i = 0,1,2,\ldots,n and the horizontal lines as j = 0,1,2,\ldots,n for an n \times n grid. Any route from corner (0,0) to corner (n,n) can only go downwards and rightwards, and so there are only two options for which corner came before corner (i,j): either corner (i-1,j) or corner (i,j-1).
(continued)

Read More

Project Euler problem 14

Source code available on GitHub.

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

    \begin{align*} n &\to n/2\ (n\textrm{ is even}) \\ n &\to 3n + 1\ (n\textrm{ is odd}) \end{align*}

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

    \[ 13 \to 40 \to 20 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 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?  \footnotesize \textbf{NOTE:} Once the chain starts the terms are allowed to go above one million.

This is a really interesting problem. Before even thinking about what we’re going to have to do later on, let’s just make a quick function to determine the next number in a Collatz sequence:

def nextCollatz(n):
    if n % 2 == 0:
        return int(n/2)
    else:
        return 3*n+1

This quite literally is nothing more than the rule given in the question. Next, we want to generate the whole sequence given a particular starting number:

def CollatzSequence(n):
    sequence = [n]
    while True:
        n = nextCollatz(n)
        sequence.append(n)
        if n == 1:
            break
    return sequence

We’re just appending the next term (using the function nextCollatz(n) we just defined) endlessly until we reach 1, and then we return that whole list.
(continued)

Read More