1. 整数問題bot

1.1. 1

一週間で解けた。いろんな副問題を知ることができた。良かった。-- ToshinoriMaeno 2016-11-21 11:56:05

https://twitter.com/handmade_math/status/797717502344056832

正の整数からなる集合Aは次の条件(1)(2)を満たす：「(1)a∈Aならばaの全ての正の約数はAに属する (2)a, b∈Aかつ1<a<bならば1+ab∈A」

Aが3個以上の要素を持つとき, 全ての正の整数がAに属することを示せ.(2005 グルジアチーム選抜テスト)

1∈Aは明らか。2∈A でないとして、3個の要素があるとすると、奇数が2個(a,b)あることになり、

1+ab は偶数となるから、矛盾する。つまり、2∈A である。

1.2. 3∈A を示す

3∈Aを否定すると、3nは含まれない。2(3n+1)+1 は3の倍数であるので、3n+1も含まれない。(not 4∈A)

3n+2 (奇数）∈Aとして、矛盾を導く。(3n+2 が偶数なら、3n/2+1 ∈A であるが、すでに否定されている）
- 例えば、5∈A ==> 2*5+1=11∈A。以下、23, 47, 95 ∈A となる。
- ところが 95 = 19*5 なので、19 (3*6+1) ∈A、矛盾である。

これがすべての 3n+2(odd)で言えれば、証明できたことになる。

11もだめ。(5の系列）

17: 35; 23: X;

29: 59, 119=7*17 でだめ。

35, 41, 47, 53, 59, 65, 71, 77, 83 : すぐに排除される。

89: 179, 359, 719, 1439, 2879 と素数が続く; 5759 = 13*443 で矛盾する。(13=1 mod 3)

5759=(12+1)*(2 * 13 * 17+1)

この先は検討中 (1,2 を除き、n 以下が含まれないとしたときに、n+1 以上が含まれないことを示す。）

/Sophie Germain prime というのを見つけた。CunnighumChainというらしい。

n=(3*2^p-1) として、3m+1 を約数に持つ (3*2^q-1) (q>=p) が存在することを示す。

2倍して1を加える操作だけでは素数が続くことはない。（既知らしい）/Nederpelt
- 1 -> 3 -> 2 -> 0 (mod 5); 4 -> 4; (3n+2 = 4 mod 5) だけを調べればよい。
該当するのは29が最小で、続くのは59, 89, 119 (7*17) で打ち切り。　89は上に書いた。
合成数には 3x+1 型の因数が含まれる。(3x+2)(3y+2)=(3z+1) となるから。これは矛盾である。

これで、n が含まれないことが示せたことになる。（nが含まれていれば、その系列に3x+1約数が出現する）

3n+2型かつ 5m+4(mod5)型の擬似素数の系列の吟味が残っている。

1.3. 1,2.3 ∈A のあと

1,2,3∈Aが示されたあとは4以上が含まれることを示すことになる。

n以下∈Aのときに、n+1∈Aを示す方針を考える。

 1+2*3 = 7; 1+2*7=15=3*5 => 5,15∈A;
 1+2*5 = 11; 1+3*5=16 => 4,8,16∈A
 1+2*4 = 9; 1+3*4=13; 1+2*8=17; ...

 6はなかなかでてこない。1+5*7=36が最小か。

 n^2 = (n-1)(n+1)+1 だから、両側がAの要素なら、n∈Aとなる。（単独の穴はない）

 素数は奇数であるので、連続して現れることはない。これくらいで、十分か。

-- ToshinoriMaeno 2016-11-15 04:46:26

MoinQ: 整数問題bot

1. 整数問題bot

1.1. 1

1.2. 3∈A を示す

1.3. 1,2.3 ∈A のあと