Problem 44 Pentagon numbers

Problem 44: Pentagon numbers

https://projecteuler.net/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 生成的数称为五边形数(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;
        }
    }
}

详细代码如下:

CPP

#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

作者:JarvisChu
原文链接:Problem 44 Pentagon numbers
版权声明:自由转载-非商用-非衍生-保持署名 | Creative Commons BY-NC-ND 3.0

发表评论