Project Euler 581

Project Euler 581

题目

47-smooth triangular numbers

A number is p-smooth if it has no prime factors larger than p.

Let T be the sequence of triangular numbers, ie T(n)=n(n+1)2.

Find the sum of all indices n such that T(n) is 47-smooth.

Størmer 定理

Størmer 定理,说明了上述定义的全体 P-smooth 数(注意这里的 P 是一个质数集合,比小于等于 p 的全体质数这种集合更普遍)中,连续两个数 n,n+1 都是 P-smooth 数的 n 的数量是有限的,并提供了一个算法查找这些 n

假设集合 P 的大小为 k,其中最大的质数为 r.

那么枚举由集合 P 中的质因子组合而成的所有无平方因子数 q(一共有 2k 个这样的 q),然后解以下佩尔方程:

x22qy2=1

那么,对这个佩尔方程的前 max(3,r+12) 个解 (xi,yi) 一一进行测试。如果 xi+12,xi12 都是 P-smooth 的,那么就找到了一个 P-smooth 对。

注意当 q=2 时,佩尔方程无解,因此需要规避这种情况。

解决方案

如果一个三角形数 n(n+1)2 p-smooth 的,那么说明 n n+1 p-smooth 的。

一开始的想法则是通过深度优先搜索直接产生所有 p-smooth 数 x,并判断 x+1 是否为 p-smooth 数。并且拟定一个枚举上限 2×1012

之后,我查阅了 Størmer 定理并直接解决本问题,至于佩尔方程的解法在 66 题已经详述。

不过,让我比较惊讶的是,Størmer 定理的实现效率会比直接搜索更低。

OEIS 上的数列 A002072 则给出了最大答案的上限。在 FORMULA 一栏中,找到

1
a(n) < 10^n/n except for n=4. (Conjectured, from experimental data.) - M. F. Hasler, Jan 16 2015

在实现 Størmer 定理时,还顺带了这个条件进行剪枝。

由于实现 Størmer 定理的效率过低,此处不附上使用它实现的代码。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M=47;
ll MX;
int pr[M+4],m=0,b[M+4];
ll ans=0;
void dfs(int f,ll x){
if(f==m+1){
ll y=x+1;
for(int i=1;i<=m&&y>1;i++)
while(y%pr[i]==0) y/=pr[i];
if(y==1) ans+=x;
return;
}
for(;x<=MX;x*=pr[f])
dfs(f+1,x);
}
int main(){
for(int i=2;i<=M;i++){
if(b[i]) continue;
pr[++m]=i;
for(int j=i+i;j<=M;j+=i)
b[j]=1;
}
MX=(m==4?4374:pow(10,m)/m);
dfs(1,1);
printf("%lld\n",ans);
}


如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
Ujimatsu Chiya 微信 微信
Ujimatsu Chiya 支付宝 支付宝