Today in one of our contests there was one difficult problem:
Define Rn is the sum of all 
such that:
p and q are positive integers, 1 ≤ p < q ≤ n
p and q are coprime. In other words, gcd(p, q) = 1
p + q ≥ n
Given the positive integer n (1 ≤ n ≤ 106), calculate R1 + R2 + ... + Rn.
I could not figure out any working solution. After the contest ended, someone mentioned a very interesting observation within his comment on the problem. That is, if we change the condition p + q ≥ n to p + q > n then Rn will always be 
(!). It was, indeed, a very obvious observation, but only on screen when we do a brute force run. I hoped for someone to come up with a mathematical explanation for it, but it seemed like no one got any ideas :D
How about you guys?
