欧拉计划44题

Pentagon numbers

Pentagonal numbers are generated by the formula, $P_n = n * (3 * n - 1) / 2$ . The first ten pentagonal numbers are:

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

It can be seen that $P_4 + P_7 = 22 + 70 = 92 = P_8$ . However, their difference, 70−22=48, is not pentagonal.

Find the pair of pentagonal numbers, $P_j$ and $P_k$ , for which their sum and difference are pentagonal and $D$ =| $P_k - P_j$ | is minimised; what is the value of $D$ ?

五边形数

五边形数由公式 $P_n = n * (3 * n - 1) / 2$ 给出。前十个五边形数是：

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

可以看出 $P_4 + P_7 = 22 + 70 = 92 = P_8$ 。然而，它们的差70−22=48并不是五边形数。

在所有和差均为五边形数的五边形数对 $P_j$ 和 $P_k$ 中，找出使 $D$ =| $P_k - P_j$ |最小的一对；此时 $D$ 的值是多少？

这个题的难度不在于求D的值，在于枚举上界，那么问题的上界是多少？

假设D就是求到的最小解

假设k比j大，那么 $P_k - P_{k - 1} >= D$ 说明k没有枚举的必要了， $P_k - P_j >= D$ 说明j没有枚举的必要了；

为什么因为D要求的是最小值，而 $P_n$ 会随着n的变大而变大那么, $P_k - P_{k - 1} = 3k - 2$ 通过发现， $P_k - P_{k - 1}$ 会随着k增大而增大；

而j是从k-1开始的，那么反过来，j越小，那么 $P_k - P_{j}$ 就越大，说明也没有枚举的必要了，假如j = k-1时， $P_k - P_j >= D$ 同理 $P_k - P_{k - 1} >= D$ ；

通过上面的两个推倒可以发现，求到的第一个满足差和都位5边形数就是最小的D值；

那么下面是代码实现：

#include <stdio.h>
#include <math.h>
#define MAX_N 1000000

double func(int x) {//五边形数的反函数
    return (sqrt(2.0 * x / 3 + 1.0 / 36.0) + 1.0 / 6.0);
}

int Pentagon(int x) {//求五边形数函数
    return x * (3 * x - 1) / 2;
}

int is_true(int i, int j) {
    long long p_k = Pentagon(i);
    long long p_j = Pentagon(j);
    double num1 = func(p_k - p_j);
    double num2 = func(p_k + p_j);
    if (num1 != floor(num1)) return 0;//没有找到他们和的五边形数
    if (num2 != floor(num2)) return 0;//没有找到他们差的五边形数
    return 1;
}


int main() {
    int flag = 0;
    for (int i = 2; i <= MAX_N; i++) {
        for (int j = i - 1; j > 0; j--) {
            if (!is_true(i, j)) continue;
            printf("%d\n", Pentagon(i) - Pentagon(j));
            flag = 1;
            break;
        }    
        if (flag) break;
    }
    return 0;
}