The Inverse Summation of Coprime Couples

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 \leq p \lt q \leq M$
$p + q \geq M$
$p$ and $q$ are coprime.

We also define $S(N)$ as the sum of $R(i)$ for $2 \leq i \leq N$.
We can verify that $S(2) = R(2) = 1/2$, $S(10) \approx 6.9147$ and $S(100) \approx 58.2962$.

Find $S(10^7)$. Give your answer rounded to four decimal places.

We can solve this by doing some mathematical observations and applying some basic Python code.

Firstly, it’s important to observe what’s happening.

1. For a given $M$, the pairs $(p, q)$ satisfying $1 \leq p < q \leq M$ and $p + q \geq M$ are exactly the pairs $(p, q)$ where $q$ is $M$ or $M − 1$, and $p < q$. 2. Then, we want pairs $(p, q)$ where $p$ and $q$ are coprime. This means they should not have any common factors apart from 1. With this, we can solve for each $M$ in the given range and sum them up. Here's a simple Python script that does this: ```python import math def R(M): return sum(1/(p*(M-p)) for p in range((M+1)//2, M) if math.gcd(p, M-p) == 1) def S(N): return sum(R(M) for M in range(2, N+1)) print(round(S(10**7), 4)) ``` This script creates functions to calculate both $R(M)$ and $S(N)$ as described in the problem. It then prints out the value of $S(10^7)$ to 4 decimal places. Note this code uses a simple for loop to iterate over all possible $p$, and the `math.gcd` function to check if the two numbers are coprime. This code may not be fast enough to compute the desired value in a reasonable time because it has to test every $p$ for every $M$ up to $10^7$. In computing the result, make sure to apply the code in an environment that supports long calculations or break the problem into manageable parts. You may need to look into optimizations, depending on your runtime constraints. Please replace the "print" line with your own code to display or use the result based on the programming language/environment you are using.

More Answers: