Project Euler个人解答(Problem 11~20)
好吧，继续来水第二篇，其实我已经做了60+道题了，但是我决定，还是把这边的进度赶完，再继续去那边刷题，不然总感觉现在放下这个坑去刷题有种奇怪的不协调感。。。
哦，说一句吧，这边只提供我的代码，我是不会直接把答案贴上来的。。せめて也要让你自己去跑一下程序的是吧~
11-20这10道题总体上不好玩，因为都是可以大量用软件自带的各种函数来计算了。。。好吧，其实不是Mathematica和Python的错。。
题目翻译摘自Project Euler 中文翻译站
Problem 11:Largest product in a grid
In the 2020 grid below, four numbers along a diagonal line have been marked in red.
08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48The product of these numbers is 26×63×78×14 = 1788696.
What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20×20 grid?
翻译：
在以下这个2020的网格中，四个处于同一对角线上的相邻数字用红色标了出来：
这四个数字的乘积是：26×63×78×14 = 1788696.
在这个20×20网格中，处于任何方向上（上，下，左，右或者对角线）的四个相邻数字的乘积的最大值是多少？
暴力解决吧。。也没啥好方法了。。
Code：Mathematica
info11=读入数据
StringSplit[info11, " "] // ToExpression;
matrix = Partition[%, 20, 20];
(Table[Times @@
Table[matrix[[i + #[[1]]*ii, j + #[[2]]*ii]], {ii, 0, 3}], {i,
4, 17}, {j, 4, 17}] // Flatten // Sort //
Last) & /@ {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0,
1}, {1, -1}, {1, 0}, {1, 1}};
Sort[%] // Last
Problem 12:Highly divisible triangular number
The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …
Let us list the factors of the first seven triangle numbers:
1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28We can see that 28 is the first triangle number to have over five divisors.
What is the value of the first triangle number to have over five hundred divisors?
翻译：
三角形数序列是由对自然数的连加构造而成的。所以第七个三角形数是1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. 那么三角形数序列中的前十个是：
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …
下面我们列出前七个三角形数的约数：
1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
可以看出28是第一个拥有超过5个约数的三角形数。
那么第一个拥有超过500个约数的三角形数是多少？
暴力解决
Code：Mathematica
NestWhile[# + 1 &, 1, Times @@ (Last /@ FactorInteger[# (# + 1)/2] + 1) < 500 &] % (% + 1)/2
Problem 13:Large sum
Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.
点击查看大矩阵
翻译：
找出以下100个50位数之和的前十位数字。
首先你要有一个支持大数计算的编程工具，不管是Mathematica或者Python都是无限支持的！！
Code：Mathematica
info13=题目数据 list13 = StringSplit[info13, "\n"]; Total@ToExpression[list13] IntegerDigits[%]~Take~10 // FromDigits
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.
翻译：
以下迭代序列定义在整数集合上：
n→n/2 (当n是偶数时)
n→3n + 1 (当n是奇数时)
应用以上规则，并且以数字13开始，我们得到以下序列：
13→40→20→10→5→16→8→4→2→1
可以看出这个以13开始以1结束的序列包含10个项。虽然还没有被证明（Collatz问题），但是人们认为在这个规则下，以任何数字开始都会以1结束。
以哪个不超过100万的数字开始，能给得到最长的序列？
注意: 一旦序列开始之后，也就是从第二项开始，项是可以超过100万的。
为了在容许时间内完成任务，需要将计算过的值标记下来，比如记录下1000对应的序列的长度，一旦别的值变换到1000的时候，可以直接加上1000的长度，后面就不用再计算了。
Code：Python
LEN_mark = [-1]*1000001;
def GetChainLength(m):
n = m;
global LEN_mark
counter = 0;
while n != 1:
if n < len(LEN_mark) and LEN_mark[n-1] != -1:
LEN_mark[m-1] = counter + LEN_mark[n-1];
return LEN_mark[m-1];
if mod(n,2):
n = 3*n+1
else:
n = int(n / 2)
counter += 1
LEN_mark[m-1] = counter;
return counter
maxlen = 0;
idx = 1;
for i in range(1,1000001):
clen = GetChainLength(i)
if clen > maxlen:
maxlen = clen;
idx = i
print idx
Problem 15:Lattice paths
Starting in the top left corner of a 2×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×20 grid?
翻译：
从一个2×2网格的左上角开始，有6条（不允许往回走）通往右下角的路。
对于20×20的网格，这样的路有多少条？
这个是小学奥数问题吧。。\(m\times n\)的话有\(C_{m+n}^{n}\)条路径。
Code：Mathematica
Binomial[40, 20]
Problem 16:Power digit sum
\(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^{15} = 32768\) 并且其各位之和为 \(3 + 2 + 7 + 6 + 8 = 26\).
\(2^{1000}\)的各位数之和是多少？
论拥有大数计算能力的编程语言的重要性，还是Python和Mathematica都可以轻松解决。
虽然自己写一个乘2的也不难。。
Code：Mathematica
IntegerDigits[2^1000] // Total
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.
翻译：
如果用英文写出数字1到5: one, two, three, four, five, 那么一共需要3 + 3 + 5 + 4 + 4 = 19个字母。
如果数字1到1000（包含1000）用英文写出，那么一共需要多少个字母？
注意: 空格和连字符不算在内。例如，342 (three hundred and forty-two)包含23个字母； 115 (one hundred and fifteen)包含20个字母。”and” 的使用与英国标准一致。
总之，神烦的一道题。。。我是手算了一边，然后Mathematica算了一遍，最后居然忘了加1000。。。
编程的话，既可以从数值计算上入手，也可以写一个API，输入数字k，返回英文，这样可以三位数调用二位数的接口，二位数调用1位数的，比较方便。
Code：Mathematica
(*接口函数*)
onetoten =
{"one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten"};
get1to10[n_] := onetoten[[n]];
elevento19 =
{"eleven","twelve","thirteen","fourteen",
"fifteen","sixteen","seventeen","eighteen","nineteen"};
get11to19[n_] := elevento19[[n - 10]];
tenn = {"twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety"};
get10n[n_] := tenn[[n - 1]];
GetNumberEnglish[n_] := Block[{},
Which[n < = 10, get1to10[n],
n <= 19, get11to19[n],
n <= 99 && Mod[n, 10] == 0, get10n[n/10],
n <= 99, GetNumberEnglish[Floor[n/10]*10] ~~ GetNumberEnglish[Mod[n, 10]],
Mod[n, 100] == 0, GetNumberEnglish[Floor[n/100]] ~~ "hundred",
True,
GetNumberEnglish[Floor[n/100]] ~~ "hundredand" ~~ GetNumberEnglish[Mod[n, 100]]]];
(*计算结果*)
StringLength[StringJoin[Table[GetNumberEnglish[i], {i, 1, 999}]]]
%+StringLength["onethousand"]
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 3That 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 23NOTE: 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)
翻译：
从下面的三角形的顶端开始，向下面一行的相邻数字移动，从顶端到底端的最大总和为23.
3
7 4
2 4 6
8 5 9 3
也就是 3 + 7 + 4 + 9 = 23.
找出从以下三角形的顶端走到底端的最大总和：
三角形见英文；
动态规划，没什么好说的吧。从下往上，逐个记录当前位置到达底端的最小距离。
Code：Mathematica
tri = {"
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"};
tri2 = StringSplit[tri, "\n"][[1]];
tri3 = ToExpression[StringSplit[#, " "] & /@ tri2];
For[i = Length[tri3] - 1, i >= 1, i -= 1,
For[j = 1, j < = Length[tri3[[i]]], j += 1,
tri3[[i]][[j]] += Max[{tri3[[i + 1]][[j]], tri3[[i + 1]][[j + 1]] }]]];
tri3 // Column
Problem 19:Counting Sundays
You are given the following information, but you may prefer to do some research for yourself.
- 1 Jan 1900 was a Monday.
- Thirty days has September,
April, June and November.
All the rest have thirty-one,
Saving February alone,
Which has twenty-eight, rain or shine.
And on leap years, twenty-nine.- A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.
How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?
翻译：
以下是一些已知信息，但是或许你需要自己做一些其他的调查。
- 1900年1月1日是星期一。
- 30天的月份有：9月，4月，6月，11月。
- 此外的月份都是31天，当然2月除外。
- 2月在闰年有29天，其他时候有28天。
- 年份可以被4整除的时候是闰年，但是不能被400整除的世纪年（100的整数倍年）除外。
20世纪（1901年1月1日到2000年12月31日）一共有多少个星期日落在了当月的第一天？
以前学过很多种算星期的算法，但是最后，我选择了Mathematica。。。orz。。
当然，还有一种方法就是\(\dfrac{1200}{7}\)。。。
Code：Mathematica
Count[Table[
DateString[{y, m, 1}, {"DayName"}], {y, 1901, 2000}, {m, 1, 12}] //
Flatten, "Sunday"]
Problem 20:Factorial digit sum
n! means n×(n-1)×…×3×2×1
For example, 10! = 10×9×…×3×2×1 = 3628800,
and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.Find the sum of the digits in the number 100!
翻译：
n! = n×(n-1)×…×3×2×1
例如，, 10! = 10×9×…×3×2×1 = 3628800,
那么10!的各位之和就是3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.
算出100!的各位之和。
Mathematica表示毫无压力。。
Code：Mathematica
IntegerDigits[100!] // Total
【完】
本文内容遵从CC版权协议，转载请注明出自http://www.kylen314.com
又看完一篇，发个言纪录一下
水吧，你就继续水吧。。
pe14：cf = Compile[{{n0, _Integer}}, Block[{n = n0}, Do[If[n == 1, Return@i]; n = If[EvenQ
, n~Quotient~2, 3*n + 1], {i, n0}] ], RuntimeAttributes -> Listable, CompilationTarget -> “C” ];Ordering, -1] // Quiet // AbsoluteTiming
pj11：bloc[n_, f_][t_] := {f @@@ #, #~Tr~f} & /@ Join @@ Partition[t, {n, n}, 1]; maxLine[t_, n_, f_: Times] := Max[bloc[n, f] /@ {t, Thread@Reverse@t}]; maxLine[a, 4]在网上搜罗到的最简单的算法。
mat =原始数据（向量）n = 4;Max@ Map[ Times @@@ {#[
], #[[All, 1]], Diagonal[#],Table[#[[k, n + 1 – k]], {k, 1, n}]} &, Partition[Partition[mat, 20, 20], {n, n}, 1], {2}]思路是用两个Partition把题设中20×20的矩阵细化为20×20个4×4的矩阵然后在每个4×4的小矩阵中对第1行，第1列，主对角线和次对角线计算（好像Mma里面没有提取次对角线的内置函数，不然可以换掉Table那一句，写出来更美观一些）
pe12:NestWhile[# + ((Sqrt[8 # + 1] – 1)/2 + 1) &, 1, Length[Divisors[#]] < 500 &]昨天留的那条是pe11，忘记标编号了，不好意思。
那啥, pe11 数据导入可以用 mat = ImportString[“08 02 … 48”, “Table”] 的说 0.0然后水平用 Times @@@ ((Partition[#, 4, 1] & /@ mat)~Flatten~1) // Max,对角用 Times @@@ Diagonal /@ ((Partition[mat, {4, 4}, 1])~Flatten~1) // Max,竖直对 Transpose@mat 考察水平, 次对角对 Reverse /@ mat 考察对角神马的~