\( p_n \)で\( n \)番目の素数を表す。また、\( \log \)は全て自然対数である。
目次
予想: 素数の2倍が素微分友愛数となることはない
pを素数とし、2pが素微分友愛数であるとする
(2p)'=p+2である
p+2が約数がすごく多くて微分すると2pに戻ってくる
pを6で割った余りで場合分けする
p=6a+1のとき
p+2=6a+3=3(2a+1)なのでこれは3の倍数になる
2a+1=bとおくと2p=(2p)''=(2a+1)+3b'となる
これが偶数ということはb'は奇数
b'=2c+1とすると
a+3c+2=pである
p=6a+1と仮定したのでa%3=2
a=3d+2とする(このときp=18d+13である)
3d+3c+4=pである
このとき明らかにc+dは奇数
p=6a-1のとき
p+2=6a+1は奇数
予想: 素数の5倍が素微分友愛数となることはない
pを素数とし、5pが素微分友愛数であるとする
(5p)'=p+5である
p+5が約数がすごく多くて微分すると5pに戻ってくる
かなりえぐい
pを5で割った余りで場合分けする
p=6a+1のとき
p+5=6a+6=2・3(a+1)
(p+2)'=3(a+1)+2(a+1)+6(a+1)'=5(a+1)+6(a+1)'=5a+5+6(a+1)'
すなわち6(a+1)'=a+1である
a+1は6の倍数なのでa=6b-1とする
このとき(a+1)'=(6b)'=5b+6b'であるから
6(a+1)'=30b+36b'>6b=a
よって矛盾が生じた
p=6a-1のとき
p%4=1なのでp=12b+5と書ける
p+5=2(6b+5)は偶数
6b+5=cとおくと(5p)''=(6b+5)+2c'となる
定理: 素数階乗は素微分友愛数にならない
素数定理
Rosser's Theoremによると、\( n \)番目の素数は\( n \log{n} \)より大きい。
また、\( n \geq 6 \)のとき、\( n \)番目の素数は\( n (\log{n} + \log{\log{n}}) \)より小さいことが知られている。
\( n (\log{n} + \log{\log{n}}) < 2n \log{n} \)であることは容易にわかる。また、数値計算と合わせて\( p_n < 2n \log{n} \)が\( n \geq 3 \)で成り立つことが分かる。
証明
10番目(29#)までの素数階乗は実験により素微分友愛数でないことが確かめられる
\( n \geq 11 \)とする
N=(n番目の素数階乗)について考えその大きさを評価する
\( N < (2n \log{n})^n \)である
\( \begin{align*} & N' \\ <& \frac{1}{2} \cdot (2n \log{n})^n \cdot n \\ =& 2^{n-1} \cdot (\log{n})^n \cdot n^{n+1} \\ =& n^{n+1 + (n-1)\log_n{2} + n\log_n{\log{n}}} \\ <& n^{n+1 + n\log_n{(2\log{n})}} \\ <& n^{n+1 + n\log_n{(2n^{0.37})}} (\because \log{n} \leq n^{\frac{1}{e}}) \\ <& n^{n+1 + 0.37n + n\log_n{2}} \\ <& n^{n+0.1n + 0.37n + 0.29n} \\ <& n^{1.76n} \end{align*} \)
\( N' \)の素因数は\( n \)より大きいので、素因数は最大でも\( 1.76n \)個しか持たない
よって\( N' \)の素因数の逆数の総和を\( T \)とすると
\( 0 < T < \frac{1.76n}{n\log{n}} = \frac{1.76}{\log{n}} \)
が成り立つ
また\( N \)の素因数の逆数の総和を\( S \)とすると
\( \begin{align*} & S \\ <& \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{p_n} \\ \leq & \sum_{k=1}^{10}\frac{1}{p_k} + \sum_{k=11}^n \frac{1}{n\log{n}} \\ <& \sum_{k=1}^{10}\frac{1}{p_k} + \int_{10}^n \frac{1}{x\log{x}} dx (\because \frac{1}{x\log{x}}は単調減少) \\ =& \sum_{k=1}^{10}\frac{1}{p_k} + \log{\log{n}} - \log{\log{10}} \\ <& \log{\log{n}} + 0.7 \\ \end{align*} \)
であるから
\( S \cdot T < \frac{1.76}{\log{n}}(\log{\log{n}} + 0.7) \)
である。
\( f(x) = \frac{1.76}{\log{x}}(\log{\log{x}} + 0.7) \)
とおくと、
\( \frac{d}{dx}f(x) = - \frac{1.76(\log{\log{x}}-0.3)}{x(\log{x})^2} \)
であるから、\( x > 4 > e^{e^{0.3}} \)で\( f(x) \)は単調減少である。
数値計算によると\( x \geq 30 \)で\( f(x) < 1 \)となるから矛盾。
よって\( 29 \)番目の素数階乗まで調べればよい。わんだほーい!!!
実験
コード
\( \left(p_n\#\right)' \)を計算するPython3のコード
# coding: utf-8 # Your code here! import sympy n = 10 primes = [] for i in range(n*n): if sympy.isprime(i): primes.append(i) if len(primes) == n: break total = 0 for p1 in primes: term = 1 for p2 in primes: if p1 != p2: term *= p2 total += term print(total) print(sympy.factorint(total))
判定法
\( 29 \)番目までの素数の逆数和が\( 2 \)に満たないこと、\( \frac{1}{7}+\frac{1}{11}+\cdots+\frac{1}{23} < 0.5 \)であることから、\( 5\# \)以降について、素因数が6個以下であれば素微分友愛数ではないことがわかる。
結果
- (2#)'=1=1
- (3#)'=5=5
- (5#)'=31=31
- (7#)'=247=13×19
- (11#)'=2927=2927
- (13#)'=40361=40361
- (17#)'=716167=19×37693
- (19#)'=14117683=37×381559
- (23#)'=334406399=43×163×47711
- (29#)'=9920878441=269×36880589
- (31#)'=314016924901=61×4253×1210397
- (37#)'=11819186711467=79×82913×1804421
- (41#)'=492007393304957=2683561×183341237
- (43#)'=21460568175640361=47×456607833524263
- (47#)'=1021729465586766997=1559×655374897746483
- (53#)'=54766551458687142251=1701437×32188409831623
- (59#)'=3263815694539731437539=1087×3002590335363138397
- (61#)'=201015517717077830328949=201015517717077830328949
- (67#)'=13585328068403621603022853=13585328068403621603022853
- (71#)'=972416614407737400870501653=653×24310877×61254579539162813
- (73#)'=71544353681891529224514036059=79×905624730150525686386253621
- (79#)'=5692733621468679832887230172131=5692733621468679832887230172131
- (83#)'=475714535349241099037539188841003=6991×17117×31727×125299823719985846887
- (89#)'=42605658161771733665696611824842057=128427649157×331748330218886478419701
- (97#)'=4156517583588203716343221884611037839=11887×349669183443106226663011851990497
- (101#)'=422113843906354093775418512493046577809=2549×165599781838506902226527466650861741
- (103#)'=43710588286712969019768170103664304877397=20831283974697087833×2098314647325937289309
- (107#)'=4701017770207212913287900722730772880277689=109×25013×45090757000504693×38239489461719284069
- (109#)'=514977313070181206962860776592994315598662571=155963971×3301899212800764139064276432106196601
以上より示された。
定理: 「飛び」ごとに素微分友愛数は高々有限個しか存在しない
直前の定理を同じように証明する。
定義
無平方数\( n \)の最大の素因数を\( p_m \)とし、\( n \)の素因数の個数を\( k \)とするとき、\( n \)の「飛び」を\( m - k \)と定義する。
直感的には、最大の素因数までで「飛ばされた」素因数の個数である。
たとえば、素数階乗の飛びは0であり、2×5×13の飛びは3である。
証明
飛びを\( a \)とし、これを固定する。また、\( N \)を飛びが\( a \)であるような無平方数とする
任意の正の数\( \varepsilon \)に対し、\( n > m \)ならば\( 2(n+a)\log{(n+a)} < n^{1+\varepsilon} \)となるような\( m \)が存在するので
このような最小の自然数\( m \)を\( L_1 \)と書くことにする
\( L_1 \)は\( \varepsilon \)と\( a \)に依存することに注意せよ
以下、\( n \geq L_1 \)とする
\( N \)に含まれる素因数が\( n \)個であるとする
このとき、\( N \)の最大の素因数は\( p_{n+a} \)であるから
$$ N' < \frac{1}{2} \cdot (2(n+a) \log{(n+a)})^n \cdot n < \frac{1}{2} n^{n(1+\varepsilon)+1} < n^{n(1+\varepsilon)+1} $$
であるから、\( N' \)は素因数を最大でも\( n(1+\varepsilon)+1 \)個しか持たない
よって\( N' \)の素因数の逆数の総和を\( T \)とすると
\( 0 < T < \frac{n(1+\varepsilon)+1}{n\log{n}} \leq \frac{1+\varepsilon+\frac{1}{L_1}}{\log{n}} \)
が成り立つ
また\( N \)の素因数の逆数の総和を\( S \)とすると
$$ 0 < S < \sum_{k=1}^{L_1}\frac{1}{p_k} - \log{\log{L_1}} + \log{\log{(n+a)}} \\ $$
が成り立つ
$$ f(x) = \left( \frac{1+\varepsilon+\frac{1}{L_1}}{\log{x}} \right) \left( \sum_{k=1}^{L_1}\frac{1}{p_k} - \log{\log{L_1}} + \log{\log{(x+a)}} \right) $$
とし、
$$ A = 1+\varepsilon+\frac{1}{L_1}, B = \sum_{k=1}^{L_1}\frac{1}{p_k} - \log{\log{L_1}} $$
とすると
$$ \frac{d}{dx}f(x) = - \frac{A(B-1+\log{\log{x}})}{x(\log{x})^2} $$
であるから、\( L_2 = \mathrm{ceil}(e^{e^{1-B}}) \)とすると
\( x \geq L_2 \)であれば\( f(x) \)は単調減少である
また、\( \lim_{n \rightarrow \infty} f(n) = 0 \)なので、ある\( L_3 \)が存在して\( x \geq L_3 \Rightarrow f(x) < 1 \)が成り立つ。
よって、\( n \geq \max(L_2,L_3) \)のとき、\( N \)は素微分友愛数ではない。
数値計算のために
\( a \)を固定し、\( \varepsilon \)を増やすと、\( L_1 \)と\( L_2 \)は増加し、\( L_3 \)は減少する。上記の定理から、\( x < \max(L_1, L_2, L_3) \)のときだけを調べればよい。よって、\( \max(L_1, L_2, L_3)) \)が最小となるように\( \varepsilon \)を取れば最適にできる。
Pythonのコード
aの値は1個ずつにしないとPaizaがタイムアウトするので注意
# coding: utf-8 # Your code here! from scipy.special import lambertw import numpy as np def f1(x, a, e): return 2 * (x + a) * np.log(float(x)) def f2(x, a, e): return x ** (1 + e) def f3(x, a, b, e): return (a / np.log(float(x))) * (b + np.log(np.log(float(x + e)))) def getls(a, e): l1 = 0 if a > 0: l1bottom = 10 l1top = 20 # e^eより大きい値をセットする while f1(l1top, a, e) > f2(l1top, a, e): l1bottom *= 2 l1top *= 2 while l1top - l1bottom > 1: l1mid = (l1bottom + l1top) // 2 if f1(l1mid, a, e) > f2(l1mid, a, e): l1bottom = l1mid else: l1top = l1mid if f1(l1bottom, a, e) > f2(l1bottom, a, e): l1 = l1top else: l1 = l1bottom else: l1 = 2 capbbottom = 1 / 2 + 1 / 3 + (1 / 2 * (np.log(np.log(float(l1))) - np.log(np.log(2.0)))) - np.log(np.log(float(l1))) capbtop = 1 / 2 + 1 / 3 + (np.log(np.log(float(l1))) - np.log(np.log(2.0))) - np.log(np.log(float(l1))) l2top = int(np.exp(np.exp(1 - capbbottom))) + 1 capa = 1 + e + 1 / l1 capb = capbtop l3bottom = l2top l3top = l3bottom * 2 while f3(l3top, capa, capb, e) > 1: l3top *= 2 while l3top - l3bottom > 1: l3mid = (l3bottom + l3top) // 2 if f3(l3mid, capa, capb, e) > 1: l3bottom = l3mid else: l3top = l3mid if f3(l3bottom, capa, capb, e) > 1: l3 = l3top else: l3 = l3bottom return [l1, l2top, l3] for a in range(1, 11): minl = 1000 mine = 0 minls = [] for e in np.linspace(0.1, 1.0000, 9001): ls = getls(a, e) l = max(ls[0], ls[1], ls[2]) if minl > l: minl = l mine = e minls = ls print(f"<tr><td>{a}</td><td>{mine}</td><td>{minls[0]}</td><td>{minls[1]}</td><td>{minls[2]}</td></tr>")
結果
\( a \) | \( e \) | \( L_1 \) | \( L_2 \) | \( L_3 \) |
---|---|---|---|---|
1 | 0.5239 | 55 | 8 | 54 |
2 | 0.5283 | 55 | 8 | 55 |
3 | 0.5312 | 56 | 8 | 56 |
4 | 0.5338 | 57 | 8 | 57 |
5 | 0.5378 | 57 | 8 | 57 |
6 | 0.5401 | 58 | 8 | 58 |
7 | 0.5422 | 59 | 8 | 58 |
8 | 0.5459 | 59 | 8 | 59 |
9 | 0.5478 | 60 | 8 | 60 |
10 | 0.5495 | 61 | 8 | 60 |
・・・数値が非常にsusである。susすぎてsus4になりそう計算過程を見直すか?