Chinese leftovers II
Problem 552
Let A_{n} be the smallest positive integer satisfying A_{n} mod p_{i} = i for all 1 ≤ i ≤ n, where p_{i} is the
i-th prime.
For example A_{2} = 5, since this is the smallest positive solution of the system of equations
- A_{2} mod 2 = 1
- A_{2} mod 3 = 2
The system of equations for A_{3} adds another constraint. That is, A_{3} is the smallest positive solution of
- A_{3} mod 2 = 1
- A_{3} mod 3 = 2
- A_{3} mod 5 = 3
and hence A_{3} = 23. Similarly, one gets A_{4} = 53 and A_{5} = 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 A_{2}, 23 divides A_{3} and 41 divides A_{10} = 5765999453. No other prime number up to 50 divides an element in A.
Find S(300000).