160217(2)

Ruby

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

昨日、
2p C p ≡ 2 C 1 mod p^4　(1)

が成り立つ素数を探そうとした。

昨日以下のコードを実行した。
（実行時間は12～18時間くらい？）

require 'prime'

def C(n, r)
  r = [r, n - r].min
  return 1 if r == 0
  return n if r == 1
  numerator = (n - r + 1..n).to_a
  denominator = (1..r).to_a
  (2..r).each{|p|
    pivot = denominator[p - 1]
    if pivot > 1
      offset = (n - r) % p
      (p - 1).step(r - 1, p){|k|
        numerator[k - offset] /= pivot
        denominator[k] /= pivot
      }
    end
  }
  result = 1
  (0..r - 1).each{|k|
    result *= numerator[k] if numerator[k] > 1
  }
  return result
end

Prime.each(500000).to_a.each{|pr|
  p pr if C(2 * pr, pr) % (pr * pr * pr * pr) == 2
}

出力結果
16843

(1)を満たすp について、既に知っている
16843
しか見つからなかったのですが、
http://mathforum.org/kb/thread.jspa?forumID=253&threadID=565740&messageID=1688842
を見ると、
この次の素数は
2124679

のようだ。

p = 2124679 のとき、

(1)を満たすことを確認しておく。

require 'prime'

def C(n, r)
  r = [r, n - r].min
  return 1 if r == 0
  return n if r == 1
  numerator = (n - r + 1..n).to_a
  denominator = (1..r).to_a
  (2..r).each{|p|
    pivot = denominator[p - 1]
    if pivot > 1
      offset = (n - r) % p
      (p - 1).step(r - 1, p){|k|
        numerator[k - offset] /= pivot
        denominator[k] /= pivot
      }
    end
  }
  result = 1
  (0..r - 1).each{|k|
    result *= numerator[k] if numerator[k] > 1
  }
  return result
end

pr = 2124679
# 条件を満たすならば出力
p pr if C(2 * pr, pr) % (pr * pr * pr * pr) == 2

出力結果
2124679