题目

Problem 421: Prime factors of n15+1

Numbers of the form n15+1 are composite for every integer n > 1.
For positive integers n and m let s(n,m) be defined as the sum of the distinct prime factors of n15+1 not exceeding m.

E.g. 215+1 = 3×3×11×331.
So s(2,10) = 3 and s(2,1000) = 3+11+331 = 345.

Also 1015+1 = 7×11×13×211×241×2161×9091.
So s(10,100) = 31 and s(10,1000) = 483.

Find ∑s(n,108) for 1 ≤ n ≤ 1011.

题解

第421题:n15+1 的素因子

对于整数 n > 1,n15+1 是合数。
对于正整数 n 和 m,记 s(n,m) 为 n15+1 所有不超过 m 的不同素因数之和。

例如,215+1 = 3×3×11×331。
因此 s(2,10) = 3, s(2,1000) = 3+11+331 = 345。

同样地,1015+1 = 7×11×13×211×241×2161×9091。
因此 s(10,100) = 31, s(10,1000) = 483。

对于 1 ≤ n ≤ 1011,求 ∑s(n,108)。

解答

其中 p 是素数。取固定的素数 p,记

为了计算 g(p),我们需要解以下同余方程:

如果 ai 是这个方程的根,则:

举例如下:

pg(p)roots
21000000000001
3999999999992
72999999999993,5,6
115000000000052,6,7,8,10
3114999999999323,6,11,12,13,15,17,21,22,23,24,26,27,29,30

于是,我们有以下 PARI/GP 程序:

f(n, m) = { z = 0; forprime(p = 2, m, a = polrootsmod(x^15+1, p);
  z += p * sum(i = 1, #a, (n+p-lift(a[i]))\p)); z}
print(f(10^11, 10^8)); quit()

相关函数说明如下:

polrootsmod(pol,p,{flag=0}): roots mod the prime p of the polynomial pol. flag is optional, and can be 0: default, or 1: use a naive search, useful for small p.

lift(x,{v}): if v is omitted, lifts elements of Z/nZ to Z, of Qp to Q, and of K[x]/(P) to K[x]. Otherwise lift only polmods with main variable v.

这个程序的运行时间是 4 分钟,不满足欧拉计划的“一分钟原则”。

优化

容易证明,当且仅当 x 是 的根时,p - x 是 的根。

令 d = gcd(15, p-1),并设 q 是 的原根,则 q1, ..., qd 是这个同余方程所有的根。进一步, 它们也是 所有的根。

举例如下:

pdqqi mod p
2111
3111
7322,4,1
11533,9,5,4,1
311577,18,2,14,5,4,28,10,8,25,20,16,19,9,1

这样,就得到以下 PARI/GP 程序:

f(n, m) = { z = 0; forprime(p = 2, m, d = gcd(15, p-1); sqrtn(Mod
  (1, p), d, &q); z += p * sum(i = 1, d, (n+lift(q^i))\p)); z }
print(f(10^11, 10^8)); quit()

相关函数说明如下:

sqrtn(x,n,{&z}): nth-root of x, n must be integer. If present, z is set to a suitable root of unity to recover all solutions. If it was not possible, z is set to zero.

这个程序的运行时间是 24 秒。