「INTEGERS: 孙智伟による素数表現関数」を確認してみた

日曜数学アドベントカレンダーの本日の記事は integers_blog さんによる「孙智伟による素数表現関数」です。
integers.hatenablog.com

大変興味深いお話なので、ぜひ多くの人に読んでいただきたいです！

この記事の $S(n)$ という関数、非常に面白いなと思いました。自然数 $n$ に対して $S(n)$ を計算すると、すべて素数になっているというのです。こういう関数を「素数表現関数」というのだそうです。

証明を見る限り、素数になるはずなのですが、それでも不思議です。本当に素数になるか確かめてみたくなったので、Ruby でプログラムを書いてみました。

# coding: utf-8

require 'prime'
require 'set'


# 孙智伟 の素数表現関数 S(n) 
# 参考：http://integers.hatenablog.com/entry/2017/12/10/000000
def sun(n)
	m = 2     # m >= 2

	while true
		pool = Set.new

		# k in [1..n] に対して 2k(k-1) を mod m ですべて計算する
		(1..n).each do |k|
			x = ( 2*k*(k-1) ) % m
			if pool.include?(x)
				break
			end
			pool << x
		end 

		# 2k(k-1) が mod m ですべて異なる
		if n == pool.size 
			return m
		end

		m += 1
	end

end

# 1 から 100 までの自然数 n に対して確認する
puts "n, S(n), \"Is S(n) a prime number?\""
(1..100).each do |n|
	# S(n) を計算する
	s_n = sun(n)

	# n, S(n), {S(n) が素数かどうか} を出力
	puts "#{n}, #{s_n}, #{Prime.prime?(s_n)}"
end

定義通り $S(n)$ を計算し、それを $n = 1, \cdots, 100$ まで計算しています。万が一、素数でない $S(n)$ が現れたら、一番右の列に "false" という文字が現れます。

さて、出力してみましょう。

$ ruby sun.rb 
n, S(n), "Is S(n) a prime number?"
1, 2, true
2, 3, true
3, 5, true
4, 7, true
5, 11, true
6, 11, true
7, 13, true
8, 17, true
9, 17, true
10, 19, true
11, 23, true
12, 23, true
13, 29, true
14, 29, true
15, 29, true
16, 31, true
17, 37, true
18, 37, true
19, 37, true
20, 41, true
21, 41, true
22, 43, true
23, 47, true
24, 47, true
25, 53, true
26, 53, true
27, 53, true
28, 59, true
29, 59, true
30, 59, true
31, 61, true
32, 67, true
33, 67, true
34, 67, true
35, 71, true
36, 71, true
37, 73, true
38, 79, true
39, 79, true
40, 79, true
41, 83, true
42, 83, true
43, 89, true
44, 89, true
45, 89, true
46, 97, true
47, 97, true
48, 97, true
49, 97, true
50, 101, true
51, 101, true
52, 103, true
53, 107, true
54, 107, true
55, 109, true
56, 113, true
57, 113, true
58, 127, true
59, 127, true
60, 127, true
61, 127, true
62, 127, true
63, 127, true
64, 127, true
65, 131, true
66, 131, true
67, 137, true
68, 137, true
69, 137, true
70, 139, true
71, 149, true
72, 149, true
73, 149, true
74, 149, true
75, 149, true
76, 151, true
77, 157, true
78, 157, true
79, 157, true
80, 163, true
81, 163, true
82, 163, true
83, 167, true
84, 167, true
85, 173, true
86, 173, true
87, 173, true
88, 179, true
89, 179, true
90, 179, true
91, 181, true
92, 191, true
93, 191, true
94, 191, true
95, 191, true
96, 191, true
97, 193, true
98, 197, true
99, 197, true
100, 199, true

たしかに、すべて素数が現れていますね！すごい！

しかも、ちゃんとすべての素数が下から順に現れていることがわかります。

$n = 1, \cdots, 300$ まで計算してみると、すべて素数であることが確認できました。 $n \leqq 300$ 以下では、 $109$ 個の素数が現れますが、 $S(300) = 599$ は $109$ 番目の素数です。