n3 + n2p = m3
とおきます。ここで、nがpの倍数と仮定しましょう。n = kpとすると、
p3 + p = (m/k)3
p3と(p + 1)3の間に立方数はないので矛盾。よってnとpは互いに素です。
さて、nは立方数です。なぜなら、nに立方数でない因子があるとするとしてそれをqとすると、n2pの項だけqが2または4個で他の項は3の倍数になるからです。n = q3として、
q9 + q6p = m3
q3 + p = (m/q2)3 = r3
p = (r - q)(r + rq + q2)
r + rq + q2は1に成り得ないから、r = q + 1で、
p = 3q2 + 3q + 1
です。
問題はこの形の素数を求めることです。上限が低いので普通に組んでも十分時間内に求まると思いますが、この形はn^2+2型の素数の列挙とほぼ同じアルゴリズムが使えます。まず、この形の自然数を並べて、
1 7 19 37 61 91 127 169 217 271
最初の項はおいておいて、2番目の項は何も考えずに素数です。n = 1だから、8, 15, ...の項を7で割れるだけ割ります。p - 1 - n = 5から5, 12, ...も同様に割ります。
1 7 19 37 61 13 127 169 31 271
次の項からも同様に処理していきます。n = 5ではp = 13だから、p - 1 - n = 7の項も13で割り切れます。
1 7 19 37 61 13 127 1 31 271
残った1ではない一度も割られていない項がこの形の素数です。詳しいアルゴリズムは、an2 + bn + cの形の素数の列挙についてそのうち書くつもりなのでそれを参照してください。
N = 106で1ms、1014で31sでした。
