正整数x, y, zが等差数列として与えられたとき、方程式
が丁度2つの解をもつ最小のnは27である。
1155は丁度10個の解を持つ最小のnである。
百万未満のnのうち丁度10個の解を持つものはいくつあるか？
まず、式を
と変形する。この時点ででなければならないことがわかる。
式を整理すると、
ここで、とおく。
との比較から、
。
また、。
あとは条件を満たす範囲でを走査して、解のカウントをインクリメントしていけばいい。
limit <- 1e6 s.count <- numeric(limit) for(x in 1:limit){ j <- 4 - (x %% 4) # j = 4k - x while(j < 3 * x && x * j < limit){ s.count[x * j] <- s.count[x * j] + 1 j <- j + 4 # k++ } } length(s.count[s.count == 10])
20秒。ただこのやり方はフォーラム見て真似したヤツです。
最初は式を
まで変形して、nの因数を全て求めた後に
かつ
を満たす因数の数をカウントするという方法で解の個数を逐一求めていたけど、それだと90秒程度かかる。
nから因数を求める代わりに先に求めておいた素数を再帰使って組み合わせてnを作るというアプローチをとっても70秒程度が限界だった。
