关于啥是Project Euler 详见 https://projecteuler.net/about      

观前声明：

1. 是个人兴趣使然的对自己入坑pe的记录，仅提供思路和部分代码；各个方面肯定都是有着优化与提升空间的，甚至在许多大佬看来这应该是初学者的浅薄而未经剪枝的丑码，如果能帮到有兴趣的人自是最好，也欢迎能醍醐灌顶的深度讨论。  

2. 大佬看到了笑笑就行，还请轻喷。

3. 带着恶意，抬杠者...俺也喷不过您，也不能拿您咋样...毕竟这只是我个人兴趣使然的行为或者说是学习记录分享。 （说是记录，但因为是早先写的所以其实是在各种意义上公开处刑和吐槽自己 并尝试补救优化）

4. 语言是c++，用的VS平台

观前提示：本期为水题。后几题出现n角形数间的科普.

第41题：

Pandigital prime

Problem 41

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime.

What is the largest n-digit pandigital prime that exists?

还是之前的定义，如果n位数由1~n组成那么这个数字就是个pandigital number（泛数字的？）比如2143是4位数的pandigital number并且还是个质数；找到最大的具有此性质的n位数质数。

首先n是小于等于9的；然后它是个质数，我们可以由此继续缩小范围；因为例子已经举了一个4位数，所以我们要找的数字肯定大于等于4位数。

我们来看5位数，每位数字之和为1+2+3+4+5=15为3的倍数，所以所有的具有此性质的5位数不可能是质数；6位数：1+2+3+4+5+6=21，8位数：1+2+3+4+5+6+7+8=36，9位数：1+2+3+4+5+6+7+8+9=45，同理，6位数，8位数，9位数都不在考虑范围内，我们要找的数只可能是4位数或7位数。

直接看7位数：

那么剩下的事就是跑一个质数表，检验所有7位数质数，把每个7位数质数变成数组表达，看是否1~7都出现了。

或者：数组从1234567开始字典排序，对于每个排序数组化为数字检验是否为质数。

关于实现这些的代码之前的题中都有而且也不难，懒得再说了撒。

ans:7652413

Coded triangle numbers

Problem 42

The nth term of the sequence of triangle numbers is given by, tn = ½n(n+1); so the first ten triangle numbers are:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 = t10. If the word value is a triangle number then we shall call the word a triangle word.

Using words.txt (right click and 'Save Link/Target As...'), a 16K text file containing nearly two-thousand common English words, how many are triangle words?

把字母A~Z对应数字1~26，那么SKY的值就等于19+11+25=55，这正好是第10个三角数（第n个三角数为n(n+1)/2），把这样的单词称为三角单词。

在words.txt：https://projecteuler.net/project/resources/p042_words.txt

网址里有近2000个英语单词，算出其中有多少个三角单词。

在22题中也需要算单词值.这题比起22可能还更简单些。单词值用char[]或者string按定义算就完事了，类似代码能在22题中找到不赘述了。

检验值是否为三角数，那不就反过来验证A=n(n+1)/2的n是否为整数，变换一下：

（(根号(8A+1))-1）/2为整数那么A就为三角数；如果不嫌麻烦也可以o(n)判断，就是在一个范围内逐个检验A是否等于某个n对应的三角数：

As：

for (n = 0; n < 50; n++)

As[n] = n * (n + 1) / 2;

int checkstr(string s,int As[50])

{

int i, length = s.size(), sum = 0;

for (i = 0; i < length; i++)

sum += s[i] - 'A' + 1;

for (i = 1; i < 50; i++)

if (sum == As[i])return 1;

return 0;

}

把近2000个单词存进string[]数组里，然后逐个检验即可。存进数组要么freopen函数读要么自己手动复制。

ans:162

第43题：

Sub-string divisibility

Problem 43

The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.

Let d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way, we note the following:

• d2d3d4=406 is divisible by 2

• d3d4d5=063 is divisible by 3

• d4d5d6=635 is divisible by 5

• d5d6d7=357 is divisible by 7

• d6d7d8=572 is divisible by 11

• d7d8d9=728 is divisible by 13

• d8d9d10=289 is divisible by 17

Find the sum of all 0 to 9 pandigital numbers with this property.

1406357289是个奇妙的数字，从2开始的连续三位数字提取出来都能被连续的质数整除，详细见上。找到所有具有此性质的由0~9组成的数字的和。

神奇归神奇，字典排序、提取数字都是之前讲过的了，该头铁该乱写还是很容易水的。

字典排序不说了，说说检验，先用数组C[]存对应要除以的质数，如果数组B[]为某个排列的0~9，那么检验函数可以这么写：

int changeinter(int A[], int start, int end)//数组提取数字之前也写过的。

{

int i, j, sum = 0;

for (i = start, j = end - start; i <= end; i++, j--)

sum += A[i] * pow(10, j);

return sum;

}

int check(int A[10])//检验函数;

{

int B[7] = { 0 }, i, C[7] = { 2,3,5,7,11,13,17 };

for (i = 0; i < 7; i++)

B[i] = changeinter(A, i + 1, i + 3);

for (i = 0; i < 7; i++)

if (B[i] % C[i])return 0;

return 1;

}

因为要求和，而我们开始就在使用数组和字典排序函数来储存全排列，所以求和可以直接用大整数的加法，因为都在数组里；

先用while把所有的0~9字典排序检验完并全部按位加到数组sum[]里，最后再进位处理：

（这里我用的之前自己写的字典排序函数，也可用algorithm库自带的next_permutation函数，相关代码及说明24题有：21~25）

while (count <= 3628800)//10!种排列;

{

if (check(A))

{

for (i = 0; i < 10; i++)

cout << A[i];

cout << endl;

for (i = 1; i <= 10; i++)

sum[i] += A[10 - i];

}

changenext(A, 10);

count++;

}

for (i = 1; i <= sum[0]; i++)

{

if (sum[i] < 10)continue;

sum[i + 1] += sum[i] / 10;

sum[i] %= 10;

sum[0] += (i == sum[0]);

}

for (i = sum[0]; i > 0; i--)

cout << sum[i];

ans：16695334890

第44题：

Pentagon numbers

Problem 44

Pentagonal numbers are generated by the formula, Pn=n(3n−1)/2. The first ten pentagonal numbers are:

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...

It can be seen that P4 + P7 = 22 + 70 = 92 = P8. However, their difference, 70 − 22 = 48, is not pentagonal.

Find the pair of pentagonal numbers, Pj and Pk, for which their sum and difference are pentagonal and D = |Pk − Pj| is minimised; what is the value of D?

五角形数：Pn=n(3n−1)/2，找到这样一对五角形数Pj和Pk，它们的和与差均为五角形数，且它们的差的绝对值D是所有的这样的五角形数对中最小的，求出D。

其实这道题俺也没啥特别好的思路，这个最小的D怎么找呢，对于一个五角形数Pk，如果所有小于它的五角形数组成的五角形数对都不具有和与差为五角形数的性质，那么若Pk与某个小于Pk的Pj具有和与差为五角形数的性质，则Pk与Pj的差的绝对值就为最小的D。

所以我们令Pk第二个五角形数开始，每次Pj都从Pk的前一个五角形数向前搜索判断是否具有此性质，一旦找到，由我们的查找规则，那么Pj与Pk的差的绝对值就是最小的D。

为了方便，我们找的时候用n1，n2作为五角形数对应的序列，n(3n−1)/2就是对应的五角形数。而检验一个数是否为五角形数也很简单，k=n(3n−1)/2变换一下：根号（1+24*k）+1为一个整数，对应代码：

int check(int np)//检验是否为五角形数;

{

double n = (pow(24 * np + 1, 0.5) + 1) / 6;

if (n == int(n))return 1;

return 0;

}

int patan(int n)//第n个五角形数

{

return n * (3 * n - 1) / 2;

}

主函数：

int main()

{

int n1, n2;

for (n1 = 2;; n1++)

{

int checkn = 0;

for (n2 = n1 - 1; n2 > 0; n2--)

{

if (check(patan(n1) + patan(n2)) && check(patan(n1) - patan(n2)))

{

checkn = 1; break;

}

}

if (checkn)break;

}

cout << n1 << " " << n2 << " " << patan(n1) - patan(n2);

return 0;

} 

由搜索规则找到的第一个五角形数对就是所求。

因为规模小，暴搜很快：答案为第2167与第1020个五角形数组成的数对。

ans：5482660

第45题：

Triangular, pentagonal, and hexagonal

Problem 45

Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:

Triangle Tn=n(n+1)/2 1, 3, 6, 10, 15, ...

Pentagonal Pn=n(3n−1)/2 1, 5, 12, 22, 35, ...

Hexagonal Hn=n(2n−1) 1, 6, 15, 28, 45, ...

It can be verified that T285 = P165 = H143 = 40755.

Find the next triangle number that is also pentagonal and hexagonal.

（tri,penta,hexa....这些前缀我都是通过某联盟知道的（雾））

三角形数：Tn=n(n+1)/2；五角形数：Pn=n(3n−1)/2；六角形数：Hn=n(2n−1)

第285个三角形数=第165个五角形数=第143个六角形数=40755。

找到下一个既是五角也是六角形数的三角形数。

完全意义上的水题...六角形是步长最大的，对后每个六角形数检验是否为三角形数或和角形数即可。注意到六角形数Hn=n(2n−1)=(2n)(2n-1)/2 所以所有的六角形数都是三角形数...只需要检验五角形数就行了。

随便跑跑：

int checkpen(long long np)//检验是否为五角形数;

{

double n = (pow(24 * np + 1, 0.5) + 1) / 6;

if (n == int(n))return 1;

return 0;

}

long long hex(long long n)

{

return n * (2 * n - 1);

}

int main()

{

long long n;

for (n = 144;; n++)

if (checkpen(hex(n)))break;

cout << hex(n);

return 0;

} 

ans：1533776805

就到这里撒。

下期就要满50题了啦~

（前提是有缘更下期）