Problem 14: Longest Collatz sequence
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.
克拉茨序列。求1000000以下的起始数字中，使克拉茨序列最长的那个。
思路：将序列中出现的每一个数字对应的长度保存在一个字典中，键值对为{起始数字：长度}，这样之后再遇到这个数字时可直接得出其长度值而不必重复计算。
比如在序列：
3→10→5→16→8→4→2→1
中，得到了比3大的多个数字的克拉茨序列长度，那么循环到这些数字时就无需再进行计算。
最后求这个字典中最大value对应的key就可以了。
#!/usr/bin/env python#创建字典colenthcolenth = {1:1}#起始数字为n时，对应的长度为collatz(n)def collatz(n): #如果n这个key不在colenth字典中，则进行以下运算，否则直接返回colength[n] if not colenth.get(n,0): if n % 2: colenth[n] = collatz(3 * n + 1) + 1 else: colenth[n] = collatz(n / 2) + 1 return colenth[n]#字典key从1循环到999999，求得所有对应的value，取最大值。m,n = 0,0for i in xrange(1,1000000): c = collatz(i) if c > m: m,n = c,iprint m,n Answer: 837799
Problem 15: Lattice paths
Starting in the top left corner of a 2x2 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 20x20 grid?
组合问题。在每一个路径中，都会有20次横向和20次纵向移动。如果把横向移动记为1，纵向移动记为0，那么问题就变成一个40位数字中有20个1和20个0的组合数。所以答案就是C2040
其实，对于一个axb的格子来说，路径数量等于Caa+b=(a+b)!/(a!·b!)
#!/usr/bin/env pythondef fact(n): if n == 1: return 1 else: return n * fact(n-1)print fact(40)/fact(20)/fact(20)
Answer 15: 137846528820
Problem 16: Power digit sum
215 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.
What is the sum of the digits of the number 21000?
#!/usr/bin/env pythondd = str(2 ** 1000)sum = 0for i in dd: sum += int(i)print sum
Answer 16: 1366
Problem 17: Number letter counts
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.
博主懒，不想做。手算。
Answer 17: 21124
Problem 18: Maximum path sum I
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
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)