150414

Ruby


Lucas、Perrin そして McIrvin

L0 = 2, L1 = 1

Ln = Ln-1 + Ln-2 for n>1

と定めると、

Lp mod p = 1

が成り立つ。

n を合成数とし、

Lp mod p = 1

が成り立つとき、

n を Lucas pseudoprime とよぶ。

これらを出力してみよう。

require 'prime'

a, b = 1, 2

i = 1

while i < 10 ** 4

  a, b = a + b, a

  i += 1

  if a % i == 1

    p i if !i.prime?

  end

end

出力結果

705

2465

2737

3745

4181

5777

6721

P0 = 3, P1 = 0, P2 = 2,

Pn = Pn-2 + Pn-3 for n>2

と定めると、

Pp mod p = 0

が成り立つ。

n を合成数とし、

Pp mod p = 0

が成り立つとき、

n を Perrin pseudoprime とよぶ。

これらを出力してみよう。

(コードも出力結果も150328分と同じ。)

require 'prime'

a, b, c = 2, 0, 3

i = 2

while i < 10 ** 6

  a, b, c = b + c, a, b

  i += 1

  if a % i == 0

    p i if !i.prime?

  end

end

出力結果

271441

904631

M0 = 5, M1 = -1, M2 = 3, M3 = -7, M4 = 11

Mn = -Mn-1 + Mn-2 - Mn-3 + Mn-5 for n>4

と定めると、

Mp mod p = p - 1

が成り立つ。

n を合成数とし、

Pp mod p = p - 1

が成り立つとき、
https://mathematrec.wordpress.com/2013/05/27/my-own-monologue-about-pseudoprimes/
にしたがい、n を McIrvin pseudoprime とよぼう。

最小の McIrvin pseudoprime は4。

よって、これより大きな McIrvin pseudoprime を出力してみよう。

（以下のコードを実行することはおすすめしない。

　i < 5000000 まで計算するのに数時間かかり、

　i < 15000000 まで計算するのに一日弱かかる。）

require 'prime'

a, b, c, d, e = 11, -7, 3, -1, 5

i = 4

while i < 15000000

  a, b, c, d, e = -a + b - c + e, a, b, c, d

  i += 1

  if a % i == i - 1

    p i if !i.prime?

  end

end

出力結果

14791044

一個しか見つからなかったが、

見つけるのが難しいことはいいことかもしれない。

この後に続く McIrvin pseudoprime を知りたければ、
オンライン整数列大辞典の

A225876（http://oeis.org/A225876/list）

を見るとよいでしょう。