Subset Sums

Let $A_q(n)$ be the number of subsets, $B$, of the set $\{1, 2, …, q \cdot n\}$ that satisfy two conditions:
1) $B$ has exactly $n$ elements;
2) the sum of the elements of $B$ is divisible by $n$.

E.g. $A_2(5)=52$ and $A_3(5)=603$.

Let $S_q(L)$ be $\sum A_q(p)$ where the sum is taken over all primes $p \le L$.
E.g. $S_2(10)=554$, $S_2(100)$ mod $1\,000\,000\,009=100433628$ and $S_3(100)$ mod $1\,000\,000\,009=855618282$.

Find $S_2(10^8)+S_3(10^8)$. Give your answer modulo $1\,000\,000\,009$.

This problem involves advanced number theory and programming concepts and cannot be solved just by hand. Here’s an outline how you could approach it:

1. Analyze the problem. You are looking for subsets of exactly $n$ elements such that the sum of the elements of this subset is divisible by $n$.

2. Notice the interesting property. If $n$ divides the sum of $n$ elements then each element can be reduced modulo $n$ and the result still stands. This means we can always reduce the elements of the set $B$ modulo $n$ and we obtain a set $\{0, 1, 2, …, n-1\}$.

3. Formulate the problem as a dynamic programming problem. You would create a 3D table where the first dimension represents the current integer in the set, the second is how many elements you have taken so far, and the third is the remainder of the sum modulo $n$.

4. Use a sieve to find all the prime numbers up to $10^8$. This will help you to execute the summation over all primes.

5. Implement a loop to compute $A_q(n)$ for each prime $n$. At the same time, you would update the result for $S_q(10^8)$ mod $1\,000\,000\,009$.

6. Do all of this for $q=2$ and $q=3$. Then the solution will be $S_2(10^8) + S_3(10^8)$ mod $1\,000\,000\,009$.

Keep in mind that the complexity of this problem requires proper optimizations, to fit into computationally feasible limits. As such, it goes beyond the usual school level of mathematics and enters the realms of competitive programming and number theory.

More Answers: