160218

Ruby

パスカルの三角形におけるp^4 を法とする合同(4)

http://mathforum.org/kb/thread.jspa?forumID=253&threadID=565740&messageID=1688842

に載っているコードで使われている数学的事実を整理してみる。

S1(n, i) を
x(x + 1) … (x + n - 1) = S1(n, 1)x + S1(n, 2)x^2 + S1(n, 3)x^3 + … + S1(n, n)x^n
と定義する。

p は3 以上の素数のとき、

2p C p ≡ 2 C 1 mod p^4

⇔ S1(p, 2) ≡ 0 mod p^3

⇔ S1(p, 3) ≡ 0 mod p^2　(※)

となるので、(※) を満たすp を探せばよい。

また、
S1(n + 1, 1)x + S1(n + 1, 2)x^2 + S1(n + 1, 3)x^3 + …
= (x + n) (S1(n, 1)x + S1(n, 2)x^2 + S1(n, 3)x^3 + …)
より、
S1(n + 1, 1) = nS1(n, 1),
S1(n + 1, 2) = nS1(n, 2) + S1(n, 1),
S1(n + 1, 3) = nS1(n, 3) + S1(n, 2)
となる。

ちなみに、Ruby で書くと以下のようになる。
（余りを用いて計算するので、以前より高速になっており、
実行時間は3時間半くらい。）

require 'prime'

# pr > 2のとき
def s3(pr)
  p2 = pr * pr
  s1, s2, s3 = 1, 1, 0
  (2..pr - 1).each{|n|
    s3 = ((n * s3) % p2 + s2) % p2
    s2 = ((n * s2) % p2 + s1) % p2
    s1 = (n * s1) % p2
  }
  s3
end

# pr = 2は、2p C p ≡ 2 C 1 mod p^4を満たさない
(Prime.each(500000).to_a - [2]).each{|pr|
  p pr if s3(pr) == 0
}

出力結果
16843