Inverse sum of coprime pairs

Revision en1, by natsukagami, 2015-08-08 21:25:44

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?

Tags inverse sum, coprime

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English natsukagami 2015-08-08 21:25:44 884 Initial revision (published)