Problem 94

辺の長さが整数の二等辺三角形で,2つの辺の長さと1つの辺の長さが1しか違わない三角形を疑正三角形(almost equilateral triangle)と呼ぶ.辺の長さが整数の正三角形の面積は整数にならないが,疑正三角形には面積が整数になるものがある(5-5-6等).周囲長が1,000,000,000以下の疑正三角形のうち面積が整数になるものの周囲長の合計を求めろという問題.
解き方が分かれば問題は何もなくて計測可能なほどの計算時間もかからなかった.ただ解き方を見つけるのに苦労するというProject Eulerっぽい問題.
三辺の長さを(a-a-b),a = b±1とする.面積はヘロンの公式(ヘロンの公式 - Wikipedia)から
\frac{1}{2}b\sqrt{a^2-\frac{1}{4}b^2}
となるので,bは偶数になる.
nを正の整数とし,b = 2n,a = 2n±1とする.
このとき面積は
n\sqrt{3n^2\pm4n+1}
で,これが整数となるためには,kを整数として
k^2=3n^2\pm4n+1
が成り立つ必要がある.変形した
(3n\pm2)^2-3k^2=1
はn=3の場合のペル方程式(ペル方程式 - Wikipedia)であり,その解からnを求められる.nからは周囲長を求められる.
x^2-3y^2=1
この方程式の最小解は(2, 1)であり,他の全ての解は次の式から求められる.
x_i+y_i\sqrt{3}=(2+sqrt{3})^i
また,ここから解についての漸化式を得られる.
x_{i+1}=2x_i+3y_i
y_{i+1}=x_i+2y_i
x=3n\pm2だが,周囲長は6n\pm2で求められる.
よってx ≡ 2 (mod 3)のとき,周囲長は2x_i-2,x ≡ 1 (mod 3)のとき,周囲長は2x_i+2となる.

limit <- 1e9
x <- 2
y <- 1
ans <- 0

repeat{
  old.x <- x
  old.y <- y
  x <- old.x*2 + old.y*3
  y <- old.x + old.y*2
  if(x %% 3 == 2){
    s <- 2*x - 2
  } else {
    s <- 2*x + 2
  }
  if(s >= limit) break
  ans <- ans + s
}
ans