Задача 428
Ожерелье из кругов

Пусть a, b и c - положительные числа.
Пусть W, X, Y, Z будут четырьмя точками, лежащими на одной прямой и такими, что |WX| = a, |XY| = b, |YZ| = c и |WZ| = a + b + c.
Пусть Cin будет кругом с диаметром XY.
Пусть Cout будет кругом с диаметром WZ.

Тройка (a, b, c) называется тройкой-ожерельем, если возможно построить k ≥ 3 различных кругов C1, C2, ..., Ck таких, что:

  • Ci не имеет общих внутренних точек с любым из Cj для 1 ≤ i, jk и ij,
  • Ci касается Cin и Cout для 1 ≤ ik,
  • Ci касается Ci+1 для 1 ≤ i < k, и
  • Ck касается C1.

Например, (5, 5, 5) и (4, 3, 21) являются тройками-ожерельями, в то время как можно показать, что (2, 2, 5) таковой не является.

Пусть T(n) будет количеством троек-ожерелий (a, b, c) таких, что a, b и c - положительные числа и bn.Например, T(1) = 9, T(20) = 732 и T(3000) = 438106.

Найдите T(1 000 000 000).

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net