ProjectEuler Problem 44: Pentagon numbers
Apr 7, 2014
Problem 44: Pentagon numbers #
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 生成的数称为五边形数(Pentagonal number)。
找到两个五边形数 Pj 和 Pk，他们的和是五边形数，他们的差也是五边形数，并且他们的差的绝对值最小。 求这个最小的差的绝对值。
方法1 遍历五边形数D，对每个D，寻找两个五边形数pk和pj，满足 pk-pj = D,pk+pj 也是五边形数，找到则停止，输出D #
核心点1，解决五边形数的判断问题 #
判断一个数 n 是否是五边形数，只要判断 n = x(3x-1)/2 的方程，有没有正整数解，即 n = x(3x-1)/2 => 3x^2 - x - 2n = 0 [1] 针对方程[1], 根据一元二次方程的求根公式 x1,x2 = (-b +- sqrt(b^2 - 4ac))/2a，带入带入 a=3,b=-1,c=-2n 得到
x1 = (1 + sqrt(1+6n)) / 6
x2 = (1 - sqrt(1+6n)) / 6
对于 x2，必然不会是正整数解，所以只需要判断 x1 即可。 实现算法如下：
// 判断 n 是否是 PentagonNumber
// 即，存在正整数 x，使得 n = x(3x-1)/2
bool isPentagonNumber(int64_t n)
{
double x = (1 + sqrt(1+24*n)) / 6 ;
if(x > 0 && (x - int64_t(x)) == 0){ // (x - int64_t(x)) == 0 表明x是整数
return true;
}
return false;
}
核心点2，解决遍历的范围问题 #
从 D = 1,5,12… 开始遍历，判断是否存在两个五边形数 pk 和 pj，满足 pk - pj = D，且 pk + pj 也是五边形数，一旦找到满足条件的pk和pj，则结束。
for(i = 1; ; i++){
D = i*(3*i-1)/2;
// 找到两个五边形数 pk, pj，满足 pk - pj = D，且 pk + pj 也是五边形数。
// 即遍历 pk， 判断 pj 和 pk+pj 是否是五边形数
}
那么如何确定 k 的范围呢？
因为 Pn - Pn-1 = 3n-2，所以随着n的增大，相邻两个五边形数的差值也就越大，相邻的最大差值不能超过D，如果超过了D，必然不满足条件。即 Pn - Pn-1 <= D，即 3n-2 <= D，即 n <= D+2/3 [2]
由方程[2] 就能确定 k 的范围了。 假设 D = pi，则 k 属于 [i+1, n]。 继而 pj = pk-D, 判断 pj 和 pk+pj 是否是五边形数即可。
for(i = 1; ; i++){
D = i*(3*i-1)/2;
// 找到 pk, pj，满足 pk - pj = D，且 pk + pj 也是五边形数。
int64_t n = (D+2)/3 + 1; // D <= 3n-2 => n
for(int64_t k = i+1; k <= n; k++){
int64_t pk = k*(3*k-1)/2;
int64_t pj = pk - pi; // pj = pk - pi
if(isPentagonNumber1(pj) && isPentagonNumber1(pj+pk) ) {
printf("find: P(k)=%lld, P(j)=%lld, D=P(i)=%lld\n", pk, pj, pi);
return 0;
}
}
}
详细代码如下：
C++ #
#include <stdio.h>
#include <stdint.h>
#include <math.h>
// 判断 n 是否是 PentagonNumber
// 即，存在正整数 x，使得 n = x(3x-1)/2
bool isPentagonNumber(int64_t n)
{
double x = (1 + sqrt(1+24*n)) / 6 ;
if(x > 0 && (x - int64_t(x)) == 0){ // (x - int64_t(x)) == 0 表明x是整数
return true;
}
return false;
}
int main()
{
for(int64_t i = 1; ; i++){
// 找到两个五边形数 pk, pj，满足 pk - pj = D，且 pk + pj 也是五边形数。
// 即遍历 pk， 判断 pj 和 pk+pj 是否是五边形数
int64_t D = i*(3*i-1)/2; // D = pi
// 方程[2]
int64_t n = (D+2)/3 + 1; // 3n-2 = D => n = (D+2)/3
// 假设 pk - pj = pi = D 则： k = i~n，j=1~n-1
// 即遍历 pk， 判断 pj 和 pk+pj 是否是五边形数
for(int64_t k = i+1; k <= n; k++){
int64_t pk = k*(3*k-1)/2;
int64_t pj = pk - D; //
if(isPentagonNumber(pj) && isPentagonNumber(pj+pk) ) {
printf("find: P(k)=%lld, P(j)=%lld, D=P(i)=%lld\n", pk, pj, D);
return 0;
}
}
}
return 0;
}
在我本机运行时，耗费了19s，才计算出答案。 所以该方法对于 golang/python 不太适用。
方法2 论坛中其它网友的答案 #
第一种，根据 pk+pj 最小来做遍历 #
solved = False
pentagonalist = set()
i = 0
while solved != True:
i += 1
psum = int(i*(3*i-1)/2)
pentagonalist.add(psum)
for pj in pentagonalist:
pk = psum - pj
if pk in pentagonalist and (pk - pj) in pentagonalist:
print("the answer is:", abs(pk-pj))
solved = True
代码可以看懂，即假设 psum = pk + pj。不断递增 psum，找满足条件的pk和pj. 不过有一点没明白，怎么确定找到的 pk-pj 就是最小的。
从代码看，程序返回时，只能确定 psum = pk+pj 最小，如果确定 pk-pj 也是最小的？
第二种，根据pk最小，来做遍历 #
#include <stdio.h>
#include <stdint.h>
#include <math.h>
// 判断 n 是否是 PentagonNumber
// 即，存在正整数 x，使得 n = x(3x-1)/2
bool isPentagonNumber(int64_t n)
{
double x = (1 + sqrt(1+24*n)) / 6 ;
if(x > 0 && (x - int64_t(x)) == 0){ // (x - int64_t(x)) == 0 表明x是整数
return true;
}
return false;
}
int main()
{
//
for(int64_t k = 1; ; k++){
int64_t pk = k*(3*k-1)/2;
for(int64_t j = 1; j < k; j++){
int64_t pj = j*(3*j-1)/2;
// 判断 pk - pj 和 pk + pj 是否是五边形数
if(isPentagonNumber(pk-pj) && isPentagonNumber(pk+pj)){
printf("find: P(k)=%lld, P(j)=%lld, D=P(i)=%lld\n", pk, pj, pk-pj);
return 0;
}
}
}
return 0;
}
和上面同样的问题，pk最小，怎么确定 pk-pj 就是最小的？
两种方法引用至此，但是我没有看懂。
答案 #
5482660
P(k)=7042750, P(j)=1560090, D=P(i)=5482660
Created At 2021-07-12 14:58