yaworsw/euler-manager

---
:id: 428
:name: Necklace of circles
:url: https://projecteuler.net/problem=428
:content: "Let <var>a</var>, <var>b</var> and <var>c</var> be positive numbers.  \nLet
  W, X, Y, Z be four collinear points where |WX| = <var>a</var>, |XY| = <var>b</var>,
  |YZ| = <var>c</var> and |WZ| = <var>a</var> + <var>b</var> + <var>c</var>.  \nLet
  C<sub>in</sub> be the circle having the diameter XY.  \nLet C<sub>out</sub> be the
  circle having the diameter WZ.\n\nThe triplet (<var>a</var>, <var>b</var>, <var>c</var>)
  is called a _necklace triplet_ if you can place <var>k</var> ≥ 3 distinct circles
  C<sub>1</sub>, C<sub>2</sub>, ..., C<sub><var>k</var></sub> such that:\n\n- C<sub><var>i</var></sub>
  has no common interior points with any C<sub><var>j</var></sub> for 1 ≤ <var>i</var>,
  <var>j</var> ≤ <var>k</var> and <var>i</var> ≠ <var>j</var>,\n- C<sub><var>i</var></sub>
  is tangent to both C<sub>in</sub> and C<sub>out</sub> for 1 ≤ <var>i</var> ≤ <var>k</var>,\n-
  C<sub><var>i</var></sub> is tangent to C<sub><var>i</var>+1</sub> for 1 ≤ <var>i</var>
  \\< <var>k</var>, and\n- C<sub><var>k</var></sub> is tangent to C<sub>1</sub>.\n\nFor
  example, (5, 5, 5) and (4, 3, 21) are necklace triplets, while it can be shown that
  (2, 2, 5) is not.\n\n![p428_necklace.png]({{ images_dir }}/p428_necklace.png)\n\nLet
  T(<var>n</var>) be the number of necklace triplets (<var>a</var>, <var>b</var>,
  <var>c</var>) such that <var>a</var>, <var>b</var> and <var>c</var> are positive
  integers, and <var>b</var> ≤ <var>n</var>. For example, T(1)&nbsp;=&nbsp;9, T(20)&nbsp;=&nbsp;732
  and T(3000)&nbsp;=&nbsp;438106.\n\nFind T(1&nbsp;000&nbsp;000&nbsp;000).\n\n"