1,2,···,nの最小公倍数の上界および素数計測関数π(n)の上界

1, 2, · · · , n の最小公倍数の上界および
素数計測関数 π(n) の上界について
風あざみ
2014/03/30
目次
1
記号の説明編
2
2
証明の準備編
3
3
1, 2, · · · , n の最小公倍数の上界編
3
4
素数計測関数 π(n) の上界編
6
5
参考にしたサイト
7
1
1
記号の説明編
[x] を x を超えない最大の整数を意味する。
また整数 n と素数 p に対して、n が pl で割り切れ pl+1 で割り切れないとき
l = vp (n) と書くことにする。
また、c < p ≤ d をみたす素数 p の積を以下のように書くことにする。
∏
p
c<p≤d
π(n) を、n 以下の正の整数のうち、素数であるものの個数とする。
1, 2,・
・
・, n の最小公倍数を lcm(1, 2, · · · , n) と書くことにする。
log x は自然対数を意味する。
2
2
証明の準備編
命題１：x, y を実数とするとき、[x + y] − [x] − [y] = 0, 1 がいえる。
証明：[x + y] − [x] − [y] ＜ (x + y) − (x − 1) − (y − 1) = 2
[x + y] − [x] − [y] ＞ (x + y − 1) − x − y = −1
[x+y]−[x]−[y] は整数だから、[x+y]−[x]−[y] = 0, 1 となる。
□
命題２：素数 p を任意にとる。このとき、以下が言える。
vp (n!) =
∞
∑
n
[ i]
p
i=1
証明：1 以上 n 以下の整数で vp (m) = i となるものの個数
=(pi の倍数の個数-pi+1 の倍数の個数)・i より
vp (n!) =
∞
∑
i=1
3
∑ n
n
n
[ i]
] − [ i+1 ]) =
i
p
p
p
i=1
∞
i・([
1, 2, · · · , n の最小公倍数の上界編
定理３：n を 9 以上の整数とするとき、以下の不等式が成立する。
)
(
n+1
n
< 4[ 2 ]−1
n+1
[ 2 ]
証明：数学的帰納法を用いて証明する。
n = 9 のとき、
( )
9
= 126, 45−1 = 256 より正しい。
5
n = 10 のとき、
( )
10
= 252, 45−1 = 256 より正しい。
5
となって定理３は正しい。
n = 2c − 1, n = 2c のとき
(
)
( )
2c − 1
2c
< 4c−1 ,
< 4c−1
c
c
が成り立つと仮定する。
3
□
n = 2c + 1 のとき
(2c+1)
(2c+1)!
(c+1)!·c!
(2c−1)!
c!·(c−1)!
=
(2c+2)!
(c+1)!·(c+1)!
(2c)!
c!·c!
=
2c + 1 2c
·
< 2 · 2 = 4 より
c+1 c
c
(
)
(
)
2c + 1
2c − 1
<4·
< 4 · 4c−1 = 4c
c+1
c
c+1
(2c−1
)=
n = 2c + 2 のとき
(2c+2)
(c+1
)
2c
c
=
2c + 2 2c + 1
·
< 2 · 2 = 4 より
c+1 c+1
(
)
( )
2c + 2
2c
<4·
< 4 · 4c−1 = 4c
c+1
c
よって、n = 2c + 1, n = 2c + 2 のときも以下の不等式が成立することがい
える。
(
n
)
[ n+1
2 ]
< 4[
n+1
2 ]−1
したがって、定理３が成り立つことがいえた。
□
正の整数 n に対して整数からなる数列 aj を以下のように定める。
a1 = n、整数 j ≥ 1 に対して、aj+1 = [
aj + 1
]
2
すると、1 ≤ · · · ≤ aj ≤ aj−1 ≤ · · · ≤ a1 = n がいえる。
正の整数 m に対して、am = 1 とする。
そして、正の整数 n に対して、以下のような関数 f (n) を考える。
( ) ( )
(
)
a1
a2
am−1
f (n) =
·
···
a2
a3
am
定理４：n を 2 以上の整数とするとき、不等式 lcm(1, 2, · · · , n) ≤ f (n) が成
立する。
証明：n 以下の素数 p を任意に取る。
vp (f (n)) =
m ∑
∞
∑
aj
aj+1
aj − aj+1
[ i]−[ i ]−[
]
p
p
pi
j=1 i=1
vp (lcm(1, 2, · · · , n)) = k とおくと、pk ≤ lcm(1, 2, · · · , n) < pk+1 となる。
k 以下の正の整数 h を任意に取る。aw+1 < ph ≤ aw をみたす、正の整数
w = w(h) が存在する。
aj
aj+1
aj − aj+1
命題１より、[ i ] − [ i ] − [
] = 0, 1 だから
p
p
pi
4
m ∑
∞
k
∑
∑
aw
aj
aj+1
aj − aj+1
aw+1
aw − aw+1
[ h]−[ h ]−[
[ i]−[ i ]−[
]
≥
]
i
p
p
p
p
p
ph
j=1 i=1
h=1
aw が偶数のとき aw+1
aw + 1
aw
、aw が奇数のとき aw+1 =
より
=
2
2
aw
がいえるから、
2
0 ≤ aw − aw+1 ≤ aw+1 がいえる。よって
aw − aw+1
aw+1
aw
0≤
≤ h < 1 ≤ h がいえるから
ph
p
p
aw+1
aw − aw+1
aw
[ h]−[ h ]−[
]≥1
p
p
ph
aj
aj+1
aj − aj+1
命題１より、[ i ] − [ i ] − [
] = 1 だから、
p
p
pi
k
k
∑
∑
aw
aw+1
aw − aw+1
[ h]−[ h ]−[
]
=
1 = k がいえる。
p
p
ph
aw+1 ≥
h=1
h=1
よって n 以下の任意の素数 p に対して vp (lcm(1, 2, · · · , n)) ≤ vp (f (n))
がいえる。したがって、f (n) が lcm(1, 2, · · · , n) で割り切れること、
つまり lcm(1, 2, · · · , n) ≤ f (n) がいえた。
定理５：n を 2 以上の整数とするとき、f (n) < 4n が成り立つ。
証明：数学的帰納法を用いて証明する。
2 ≤ n ≤ 8 のとき
n = 2 のとき
f (2) =
n = 3 のとき
n = 4 のとき
( )
2
= 2, 42 = 16
1
( ) ( )
3
2
f (3) =
·
= 6, 43 = 64
2
1
( ) ( )
4
2
f (4) =
·
= 12, 44 = 256
2
1
n = 5 のとき
f (5) =
( ) ( ) ( )
5
3
2
·
·
= 60, 45 = 1024
3
2
1
n = 6 のとき
( ) ( ) ( )
6
3
2
f (6) =
·
·
= 120, 46 = 4096
3
2
1
5
□
n = 7 のとき
f (7) =
( ) ( ) ( )
7
4
2
·
·
= 420, 47 = 16384
4
2
1
n = 8 のとき
( ) ( ) ( )
8
4
2
f (8) =
·
·
= 840, 48 = 65536
4
2
1
となって定理５は正しい。
8 ≤ n < r のとき、定理５が正しいと仮定する (ただし、r は 9 以上の整数)。
n = r のとき
r が偶数のとき a2 =
a2 ≤
r
r+1
、r が奇数のとき a2 =
だから
2
2
r+1
<r
2
だから、帰納法の仮定より
f (a2 ) =
( )
(
)
a2
am−1
···
< 4a2
a3
am
ここで定理４より、
( )
a1 +1
a1
< 4[ 2 ]−1 = 4a2 −1 がいえるから
a2
( ) ( )
(
)
a1
a2
am−1
·
···
< 4a2 · 4a2 −1 = 42a2 −1 ≤ 4a1 = 4r
a2
a3
am
すなわち、f (r) < 4r がいえる。
したがって、n = r のときも定理５がいえる。
以上より、定理５は正しいことが示された。
□
定理４と定理５より、以下が分かる。
n ≥ 2 のとき、lcm(1, 2, · · · , n) < 4n が成り立つ。
4
素数計測関数 π(n) の上界編
定理６：n を 2 以上の整数とする。π(n) は以下の不等式をみたす。
π(n) < 4 log 2 ·
n
log n
証明：n 以下の素数 p を任意に取るとき、lcm(1, 2, · · · , n) を素因数分解し
たときの p の指数を k とおくと、pk ≤ n < pk+1 となる。
6
n < pk+1 ≤ p2k より、n1/2 =
4n ＞ lcm(1, 2, · · · , n) =
√
n < pk がいえるから
∏
pk >
1<p≤n
∏ √
1
n = n 2 π(n)
1<p≤n
1
したがって、π(n) · log n < log 4n = 2n log 2
2
n
がいえた。
よって、π(n) < 4 log 2 ·
log n
5
参考にしたサイト
http://www.renyi.hu/~p_erdos/1934-01.pdf
7
□

Download Report