题目

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.

解答

$\sum_{n=1}^{10^{11}}s(n,10^8)=\sum_{1\le{n}\le{10^{11}}}\sum_{\substack{p{\le}10^8\\p|n^{15}+1}}}p=\sum_{p{\le}10^8}\sum_{\substack{1{\le}n{\le}10^{11}\\p|n^{15}+1}}p$

$g(p)=\sum_{\substack{1{\le}n{\le}10^{11}\\p|n^{15}+1}}p=p\sum_{\substack{1{\le}n{\le}10^{11}\\p|n^{15}+1}}1$

$n^{15}+1{\equiv}0\pmod p$

$g(p)=p\sum_{a_i}\lfloor\frac{10^{11}+p-a_i}{p}\rfloor$

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

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.

优化

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

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.