def farey_sequence(n): a, b, c, d = 0, 1, 1, n yield (a, b) while (c <= n): k = (n + b) // d a, b, c, d = c, d, k * c - a, k * d - b yield (a, b) def a085582(n): count = 0 for s, r in farey_sequence(n - 1): if r == 1: continue h = w = n - r - s while h > 0 and w > 0: h1, w1 = h, w while h1 > 0 and w1 > 0: count += h1 * w1 h1 -= s w1 -= r h -= r w -= s count *= 2 count += (n-1)**2 * n * (2*n-1) // 6 return count