(a, b, c)を各辺の長さが整数であるような直角三角形の各辺の長さとする。このとき、この直角三角形を4つ組み合わせることで、直角三角形の長辺cを1辺の長さとする正方形を作ることができる(上記問題文リンク先参照)。
例えば、(3, 4, 5)の三角形は5×5のサイズの正方形を作る。このとき、中央に1×1サイズの正方形の穴ができるが、この正方形を用いて元の5×5の正方形を敷き詰めることができる。
しかし、(5, 12, 13)の三角形の場合は中央の穴は7×7であり、13×13の正方形を敷き詰めることはできない。
周囲長が1億未満である直角三角形のうち、このような敷き詰めが可能なピタゴラス三角形はいくつあるか。
とし、
とする。
長辺は他の2辺の差で割り切れなければならないので、ある正整数nをもってきて
これを整理すると
となって、ペル方程式が出てくる。
周囲長pは
とおくと
と表すことができる。
はもしd = 1のときに成立するならaを調整することで任意の正整数dについて成立させられる。そのための条件はxが奇数であることだが、ペル方程式
の解の漸化式は
であり、最小解は(1, 1)なのでxは常に奇数となる。
よって、dはd(x + n)が1億未満である範囲で自由にとることができる。
lim <- 1e8 ## (x, y) = (1, 1) => a = 0なので最小解だけ飛ばす x <- 3 n <- 2 cnt <- 0 while(x + n < lim){ if(x^2 - 2*n^2 == -1) cnt <- cnt + floor(lim / (x + n)) oldx <- x x <- x + 2*n n <- oldx + n } cnt
170μsくらい。
