いくつかの素数pには
が立方数となるような自然数nが存在する。
例えば、p=19のとき、n=8であり、。
このような性質をもつ素数pに対するnは一意に定まる。また、100未満の素数に限るとこのような素数は4つしかない。
100万未満の素数のうち、上述の性質をもつものはいくつあるか？
まず、与えられた式を次のように変形する。
...(1)
次に、nの因数を、その指数を3で割ったときの余りが0のもの、1のもの、2のものの3グループに分け、nを次のように記述する。
このとき、は次のように因数分解できなければならない。
ここでkは自然数である。式を整理すると、
右辺は合成数ではないので、
である。結局、
であり、kもmも自然数であるから、立方数の差で表すことのできる素数を求めればよいことになる。
今回は自力でいけた。
library(gmp) cnt <- 0 for(x in 2:577){ for(a in 1:(x-1)){ if(isprime(x^3 - a^3)) cnt <- cnt + 1 } } cnt
1.9秒。
ただ
cnt <- 0 m <- 1 while((p <- (m+1)^3 - m^3) < 1e6){ if(isprime(p)) cnt <- cnt + 1 m <- m + 1 }
でも正しい答えが出るし、圧倒的に早い(<10ms)し、なんとなくこれで間違いないような気もするのでもう少し考える。
(追記)
何のことはない立方数の差は
だから立方数の差が素数であるためには2つの立方数の根の差が1じゃないとダメなわけですね。自力で思いつく前にフォーラム開いてしまいました…。
