I've been working on this for a while and found several solutions so far, but none are fast enough to find the necessary $S(10^7)$. Here is the question:
For an integer $M$, we define $R(M)$ as the sum of $1/(p \cdot q)$ for all the integer >pairs p and q which satisfy all of these conditions:
- $1 ≤ p < q ≤ M$
- $p + q ≥ M$
- $p$ and $q$ are coprime.
We also define $S(N)$ as the sum of $R(i)$ for $2 ≤ i ≤ N$. We can verify that $S(2) = R(2) = 1/2, S(10) ≈ 6.9147$ and $S(100) ≈ 58.2962$.
Find $S(10^7)$. Give your answer rounded to four decimal places.
My most recent and fastest solution loops through the fractions in the Farey Sequence and for each $a/b$ it adds $(min(a,N-b) +1)/(a \cdot b)$ to the total. (Actually it loops through half of them, taking into account that if $a/b$ is reduced, so is $(b-a)/b$). It takes just over an hour to compute $S(10^6)$.
Now, recently, I stumbled across the Stern-Brocot tree which has a certain property which could help me. If $p_1/q_1,p_2/q_2,...,p_n/q_n$ are all the rationals at the same depth in the Stern–Brocot tree, then
$\sum\limits_{k=1}^n \dfrac{1}{p_k \cdot q_k} = 1$
Adjusting this for what the problem needs, the sum of $1/(p \cdot q)$ for any row branching off of $1/2$ will be equal to $1/2$. The only problem is finding out which rows and partial rows will fit the requirements of the problem. Thanks, any help is greatly appreciated!
EDIT: Someone on reddit pointed out that if we changed $p+q \geq M$ to $p+q > M$, each sum, $R(M)$, would be exactly $1/2$. So all that remains is to calculate the extra cases where $p+q=M$. This will add $1/(a \cdot b)$ for every member, $a/b$,of the Farey sequence where $p + q \leq N$ exactly once. I updated my code to just multiply $1/2$ by $N-1$ and then loop through the Farey sequence and add the extra terms which slightly improved my code, but not substantially. I still need to find a way to do this without looping through everything.