PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 510 / 3つの接する円

円 A と B がお互いに,そして線分 L と異なる3点で接している。
円 C は A, B, L で囲まれた領域の内部にあり,3つすべてに接している。A, B, C の半径をそれぞれ rA, rB, rC としよう。

f:id:variee:20170609222232p:plain

0 < rA ≤ rB ≤ n に対して S(n) = Σ(rA + rB + rC) とする。rA, rB, rC は整数とする。0 < rA ≤ rB ≤ 5 のときの解は rA = 4, rB = 4, rC = 1 のみであり,
S(5) = 4 + 4 + 1 = 9

また,S(100) = 3072 が与えられている。

S(10^9) を求めよ。

Problem 510 - Project Euler


3円の半径を a, b, c (c≦a≦b)とおくと,受験数学でおなじみの「直角三角形を作る」「1つのものを2通りに表す」で c が表せます。

 \sqrt{ac}+\sqrt{bc}=\sqrt{ab}

 \therefore c=\dfrac{ab}{a+b+2\sqrt{ab}}

a と b の値でループさせて c が整数になる組を探す解法では時間内に解けないことは明らかなので a, b, c の形はもっとしぼりこめるはずです。a, b の最大公約数を g として

 a=gA,\, b=gB,\, (A,\, B)=1

とおきます。

 c=\dfrac{AB}{A+B+2\sqrt{AB}}\cdot g

√(AB)のルートは外れるので,AB は平方数です。(A, B)=1 から A, B は両方とも平方数だとわかるので

 a=p^2,\, b=q^2,\, (p,\, q)=1

とおきます。c の式に代入すると

 c=\left(\dfrac{p q}{p+q}\right)^2 g

これは整数ですが,pq と p+q は互いに素です。カッコ内の分数は約分できないので,g は (p+q)^2 の倍数です。

以上をまとめましょう。

 a=kp^2(p+q)^2,\, b=kq^2(p+q)^2,\, c=kp^2q^2

このあとの計算方法は問題75とほぼ同じです。

  1. k=1 の項を求める
  2. k の最大値を求める
  3. k=1 の項を k(k+1)/2 倍して足しあわせる

p, q の候補が177個しかなく,0.1秒で答えが出ました。


variee.hatenadiary.com