Problem 552
Chinese leftovers II
Let An be the smallest positive integer satisfying An mod pi = i for all 1 ≤ i ≤ n, where pi is the i-th prime.
For example A2 = 5, since this is the smallest positive solution of the system of equations
- A2 mod 2 = 1
- A2 mod 3 = 2
The system of equations for A3 adds another constraint. That is, A3 is the smallest positive solution of
- A3 mod 2 = 1
- A3 mod 3 = 2
- A3 mod 5 = 3
and hence A3 = 23. Similarly, one gets A4 = 53 and A5 = 1523.
Let S(n) be the sum of all primes up to n that divide at least one element in the sequence A.
For example, S(50) = 69 = 5 + 23 + 41, since 5 divides A2, 23 divides A3 and 41 divides A10 = 5765999453. No other prime number up to 50 divides an element in A.
Find S(300000).
中国剩余定理II
记An为满足An mod pi = i对所有1 ≤ i ≤ n成立的最小正整数，其中pi表示第i个素数。
例如，A2 = 5，因为5是如下方程组的最小正整数解
- A2 mod 2 = 1
- A2 mod 3 = 2
A3需要多满足一个方程，也就是说，A3是如下方程组的最小正整数解
- A3 mod 2 = 1
- A3 mod 3 = 2
- A3 mod 5 = 3
因此A3 = 23。同样地我们能够得到A4 = 53以及A5 = 1523。
记S(n)为所有小于等于n且至少整除序列A中一个元素的素数之和。
例如，S(50) = 69 = 5 + 23 + 41，因为5整除A2，23整除A3，以及41整除A10 = 5765999453。其它小于等于50的素数都不能整除A中的任意一个元素。
求S(300000)。