Problem 428

Problem 428 「円のネックレス」 †

a, b, c を正の整数とする.
|WX| = a, |XY| = b, |YZ| = c, |WZ| = a + b + c となる同一直線上の四点 W, X, Y, Z があるとしよう.
XY を直径とする円を Cin とする.
WZ を直径とする円を Cout とする.

k ≥ 3 のときに k 個の円 C1, C2, ..., Ck を以下のように配置できるとき, 三つ組 (a, b, c) をネックレス三つ組と呼ぶ.

• Ci は 1 ≤ i, j ≤ k かつ i ≠ j において, いかなる Cj とも共有する内点を持たない.
• Ci は 1 ≤ i ≤ k において, Cin, Cout と共に接している.
• Ci は 1 ≤ i < k において, Ci+1 に接している.
• Ck は C1 に接している.

例えば, (5, 5, 5) と (4, 3, 21) はネックレス三つ組であり, (2, 2, 5) はそうではないことも示される.

a, b, c が正の整数でかつ b ≤ n のときのネックレス三つ組の個数を T(n) としよう. 例えば, T(1) = 9, T(20) = 732, T(3000) = 438106.

T(1 000 000 000) を求めよ.