## Project Euler problem 18

Source code available on GitHub.

3
7 4
2 4 6
8 5 9 3

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

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

## Project Euler problem 17

Source code available on GitHub.

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 to ( 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)

## Project Euler problem 16

Source code available on GitHub.

Easy. Define a quick digits function to return a tuple of the digits of N:

def digits(N):
return tuple(int(i) for i in str(N))

Now just sum the digits of . Done.

def digits(N):
return tuple(int(i) for i in str(N))

print(sum(digits(2**1000)))

(continued)

## Project Euler problem 15

Source code available on GitHub.

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 and the horizontal lines as for an grid. Any route from corner to corner can only go downwards and rightwards, and so there are only two options for which corner came before corner : either corner or corner .
(continued)

## Project Euler problem 14

Source code available on GitHub.

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)