BruteFourFours

概要

2015/04/20

2011年に作ったJavaScriptによる4つの4では、5000以下の自然数のうち4998個を見つけることができた。ここでは更にスクリプトを改良して5000以下で未発見だった2個の解決と、10000以下および20000以下の解決状況について紹介する。

今回多倍長化を試みるきっかけとなる、有効精度を超えた解を教えて頂いたfour four's の部屋様(Twitter)には大変感謝したい。

スクリプトの改良

2015/04/20

基本的な4つの4の解き方は以前のものに準じる。今回は10000以下まで範囲を広げるために本来の4つの4にあった小数点を循環小数を追加している。

• .4 = 0.4
• .4・ = 0.44444...

これを使うと総和Σを使用しない本来バージョンの1〜100までの結果を得ることができる。

Val : formula 
1 : 4/(4+4-4)
2 : 4-(4+4)/4
3 : (4+4+4)/4
4 : √(4+4+4+4)
5 : (4+4*4)/4
6 : 4+(4+4)/4
7 : 44/4-4
8 : 4+4+4-4
9 : 4+(4!-4)/4
10 : (44-4)/4
11 : 4+(4+4!)/4
12 : (4+44)/4
13 : √4+44/4
14 : √4+4+4+4
15 : 4+44/4
16 : 4+4+4+4
17 : (4!+44)/4
18 : 4+4*4-√4
19 : 4!-(4!-4)/4
20 : 4+4!-(4+4)
21 : 4!-4!/(4+4)
22 : √4+4+4*4
23 : (4*4!-4)/4
24 : 4+4+4*4
25 : (4+4*4!)/4
26 : 4!+(4+4)/4
27 : 4!+4!/(4+4)
28 : 4*(4+4)-4
29 : 4!+(4!-4)/4
30 : 4*(4+4)-√4
31 : 4!+(4+4!)/4
32 : 4*4+4*4
33 : (√4+√√((√4)^4!))/√4
34 : √4+4*(4+4)
35 : 4!+44/4
36 : 4+4*(4+4)
37 : 4!+(√4+4!)/√4
38 : 44-(√4+4)
39 : 44-√4/.4
40 : 4*(4+√4+4)
41 : √((4!+(4+4)!)/4!)
42 : √4+44-4
43 : (4!-4)/.4・-√4
44 : 4+44-4
45 : (√4+4)!/(4*4)
46 : 4+44-√4
47 : (4*4!-√4)/√4
48 : 4*(4+4+4)
49 : ((4+4!)/4)^√4
50 : √4+4+44
51 : (4!-√4)/.4-4
52 : 4+4+44
53 : 4/.4・+44
54 : (√4+4)^4/4!
55 : 44/(.4*√4)
56 : 4!+4*(4+4)
57 : 4!+4!+4/.4・
58 : (4^4-4!)/4
59 : (4+4!)/.4・-4
60 : 4*4*4-4
61 : (4+4!)/.4・-√4
62 : 4*4*4-√4
63 : (4^4-4)/4
64 : (4+4)*(4+4)
65 : (4+4^4)/4
66 : √4+4*4*4
67 : 4+(4+4!)/.4・
68 : 4+4*4*4
69 : 4+(√4+4!)/.4
70 : (4!+4^4)/4
71 : (4!+4!-√(.4・))/√(.4・)
72 : 4+4!+44
73 : 4/.4・+√√((√4)^4!)
74 : √4+4*4!-4!
75 : 44/.4・-4!
76 : 4*(4!-4)-4
77 : (4/.4・)^√4-4
78 : 4*(4!-4)-√4
79 : (4/.4・)^√4-√4
80 : 4*(4+4*4)
81 : (4!/(4+4))^4
82 : √4+4*(4!-4)
83 : √4+(4/.4・)^√4
84 : 4+4*(4!-4)
85 : 4+(4/.4・)^√4
86 : √4*44-√4
87 : 4*4!-4/.4・
88 : 44+44
89 : 4!+(√4+4!)/.4
90 : 4*4!-(√4+4)
91 : 4*4!-√4/.4
92 : 4+√4*44
93 : 4*4!-√(4/.4・)
94 : √4+4*4!-4
95 : 44/.4・-4
96 : 4+4*4!-4
97 : 44/.4・-√4
98 : 4-√4+4*4!
99 : (4!+4!-4)/.4・
100 : 4*(√4+4!)-4

プログラムの計算上の改良として、以前は一変数演算子と二変数演算子を指定した配列のデータに一律に作用させ結果を弾いていたのだが、データが小さい順に並んでいるなら計算量を節約できる。例えばあるデータに総和を作用させて数値上限を超えてしまったら、その次のデータはもっと大きな結果になるので以降を全てスキップすることができる。二変数演算子の加算・乗算も同じことが言える。除算や減算などは、計算が負になったり1を切った時に前後を入れ替えて計算を続けることで、前後を入れ替えた演算子を単に2回作用させるよりも半分のコストで済む。

プログラムはStage1〜Stage4までの段階で進み、Stage1で1個使った組み合わせ、Stage2ではStage1の結果同士に二変数演算子を作用させて作った2個の組み合わせ、Stage3ではStage1とStage2の結果に二変数演算子を作用させた3個の組み合わせ、最後のStage4ではStage1+Stage3またはStage2+Stage2を組み合わせて4つの4を作る。二変数演算子を作用させたあと指定回数の一変数演算子を作用させて候補を豊かにする。

計算コストは候補数が増えていく後半に行くほど増大するが、最後のStage4では二変数演算子を作用させた後に一変数演算子(平方根・階乗・総和)を作用させて値が減る演算子は平方根しかない。しかも平方根はほとんど意味のない無理数ばかり返すのでこれを無視してしまうことによって、Stage4では欲しい数より大きな結果を事前に消去できるようになった。そのためプログラムには各Stageごとに上限値を設定できるようになっている。また無理数の平方根を許可するフラグは無効化してある。

4つの4スクリプトver.2.2

2:√4
3:Σ(√4)
4:4
6:(Σ(√4))!
10:Σ4
21:Σ((Σ(√4))!)
24:4!
55:ΣΣ4
231:ΣΣ((Σ(√4))!)
300:Σ(4!)
720:((Σ(√4))!)!
1540:ΣΣΣ4
26796:ΣΣΣ((Σ(√4))!)
45150:ΣΣ(4!)
259560:Σ(((Σ(√4))!)!)
1186570:ΣΣΣΣ4
3628800:(Σ4)!
359026206:ΣΣΣΣ((Σ(√4))!)
1019283825:ΣΣΣ(4!)
33685826580:ΣΣ(((Σ(√4))!)!)
703974775735:ΣΣΣΣΣ4
6584096534400:Σ((Σ4)!)

3947 : Σ((Σ4)!)%√((√4)^4!)-Σ((Σ(√4))!)

8563 : Σ(√4)+Σ(.4・*((Σ(√4))!)!)/(Σ(√4))!

多倍長化スクリプト

2015/04/20

10000以下で発見できない15個、特に5000以下で見つからない3527を発見するため、今回新たに多倍長演算を組み込んだスクリプトを作成した。

sHugeIntはJavaScript-多倍長演算ライブラリの成果をフィードバックした小規模な多倍長演算をサポートする。始めは開発途中のHugeFloat alpha12を完成させて、任意精度多倍長浮動小数点を扱えるスクリプトを作成したが、これは非常に重く実用にならなかった。sHugeIntでは任意精度の演算をあえて切り捨て、7桁配列4個で作ることができる28桁の自然数の計算に特化している。実装された演算は以下の通り。

平方根は通常の数値型の範囲内だけで扱い、多倍長ではサポートしない。多倍長になるサイズの数値の平方根が自然数になるようなケースを切り捨てたためである。

この小規模なライブラリを使用することで、扱う数の大きさによって通常の数値型と多倍長型を切り替えるのではなく、すべての計算を多倍長型で行うようになった。4つの4スクリプトver.3.1が多倍長化した4つの4スクリプトだ。このスクリプトはsHugeIntがサポートしない小数を扱うことができないが、前項の通り小数が必要な数は通常の数値型を使うスクリプトが見つけられた9985個このうち1個だけで、多倍長化によってカバーできると判断した。

計算できる上限が2の53乗(16桁)から28桁になったことで、4を1つだけ使う候補は22個から7個増えて29個になる。

2:√4
3:Σ(√4)
4:4
6:(Σ(√4))!
10:Σ4
21:Σ((Σ(√4))!)
24:4!
55:ΣΣ4
231:ΣΣ((Σ(√4))!)
300:Σ(4!)
720:((Σ(√4))!)!
1540:ΣΣΣ4
26796:ΣΣΣ((Σ(√4))!)
45150:ΣΣ(4!)
259560:Σ(((Σ(√4))!)!)
1186570:ΣΣΣΣ4
3628800:(Σ4)!
359026206:ΣΣΣΣ((Σ(√4))!)
1019283825:ΣΣΣ(4!)
33685826580:ΣΣ(((Σ(√4))!)!)
703974775735:ΣΣΣΣΣ4
6584096534400:Σ((Σ4)!)
64449908476890321:ΣΣΣΣΣ((Σ(√4))!)
519469758462957225:ΣΣΣΣ(4!)
51090942171709440000:(Σ((Σ(√4))!))!
567367456205760161490:ΣΣΣ(((Σ(√4))!)!)
247790242435923759782980:ΣΣΣΣΣΣ4
620448401733239439360000:(4!)!
21675163587152337239947200:ΣΣ((Σ4)!)

このスクリプトを使用して10000以下を検索すると、なんと10000個中9999個まで見つけることができる。未発見の15個の数字の計算結果は以下の通りとなった。

3527:ΣΣΣΣΣ((Σ(√4))!)%Σ(4*4!)-Σ4
5297:(ΣΣΣΣ(4!)-4*4)%ΣΣΣ((Σ(√4))!)
7397:Σ(ΣΣΣΣΣ((Σ(√4))!)%((Σ(√4))!)!)/Σ(√4)-ΣΣ(4!)
7463:ΣΣ(4!)/Σ((Σ(√4))!)+ΣΣΣΣ(4!)%ΣΣΣ((Σ(√4))!)
7817:(Σ((Σ(√4))!))!%(Σ(Σ(4!)-√4)-√4)
8273:((Σ4)!)^4%ΣΣ(4!-√4)
8363:ΣΣΣΣ(4!)%ΣΣ(Σ4+4!)-√4
8429:((4!)!-Σ(Σ4+ΣΣΣ((Σ(√4))!)))%ΣΣ(4!)
8819:ΣΣΣΣΣ((Σ(√4))!)%(ΣΣΣ((Σ(√4))!)-((Σ(√4))!)!)-Σ4
9113:(Σ(((Σ(√4))!)!)*(Σ((Σ(√4))!))!)%Σ(Σ(4!)-√4)
9353:Not Found
9413:((Σ((Σ(√4))!))!%ΣΣΣΣΣ4)%ΣΣ(4!)-√4
9497:(4+Σ((ΣΣ4)^(Σ(√4))!))%ΣΣΣ((Σ(√4))!)
9533:(ΣΣΣΣ(4!)/Σ((Σ(√4))!))%ΣΣ(((Σ(√4))!)^√4)
9833:Σ(ΣΣΣΣΣΣ4%Σ(4!))/4-√4

3527が見つかったことにより、5000以下の全ての自然数は4つの4で表せるようになった。

また循環小数を使わないと表せなかった8563も自然数だけで計算できる。

8563 : (ΣΣΣΣΣΣ4%(ΣΣ(4!)-Σ(√4)))/4

9353はこの記事を書いている時点では依然として見つかっていない。9353は冪剰余を導入した次の改良で発見された。(2015/04/23)

10000以下の計算には手元のGoogleChrome上で2196秒を要したが、その内訳を表にしておく。classifyは演算子を作用させて作られた新しい数式を加えた全候補から、各値ごとに最も複雑性の低いものだけを選んで残りを捨てる操作である。

見ての通り、計算時間の大部分がStage4A1の除算と剰余に費やされており、ここだけで発生する候補数が300万個に達している。これは剰余を利用して任意の4桁の数を作る操作なのである。新たに作られた14個の数のうち特に難解な剰余を使ってできたものを展開してみよう。

5297:(ΣΣΣΣ(4!)-4*4)%ΣΣΣ((Σ(√4))!)
 = (519469758462957225-16)%26796

7397:Σ(ΣΣΣΣΣ((Σ(√4))!)%((Σ(√4))!)!)/Σ(√4)-ΣΣ(4!)
 = Σ(64449908476890321%720)/3-45150 = Σ(561)/3-45150

7817:(Σ((Σ(√4))!))!%(Σ(Σ(4!)-√4)-√4)
 = 51090942171709440000%(44551-2)

8273:((Σ4)!)^4%ΣΣ(4!-√4)
 = 173401213127727513600000000%32131

8363:ΣΣΣΣ(4!)%ΣΣ(Σ4+4!)-√4
 = 519469758462957225%177310-2

8429:((4!)!-Σ(Σ4+ΣΣΣ((Σ(√4))!)))%ΣΣ(4!)
 = (620448401733239439360000-359294221)%45150

8819:ΣΣΣΣΣ((Σ(√4))!)%(ΣΣΣ((Σ(√4))!)-((Σ(√4))!)!)-Σ4
 = 64449908476890321%(26796-720)-10

9113:(Σ(((Σ(√4))!)!)*(Σ((Σ(√4))!))!)%Σ(Σ(4!)-√4)
 = (259560*51090942171709440000)%44551

9413:((Σ((Σ(√4))!))!%ΣΣΣΣΣ4)%ΣΣ(4!)-√4
 = (51090942171709440000%703974775735)%45150-2

9497:(4+Σ((ΣΣ4)^(Σ(√4))!))%ΣΣΣ((Σ(√4))!)
 = (4+383108932719040515625)%26796

9533:(ΣΣΣΣ(4!)/Σ((Σ(√4))!))%ΣΣ(((Σ(√4))!)^√4)
 = (519469758462957225/21)%222111

このような人間には思いつかないような巨大自然数を利用した剰余計算を力づくで計算することで、最も難しい15個のうち14個が解決されたのだ。1000以下のおとなしい解が人間に思いつかない技巧的な答えをスクリプトが生み出すものだとするなら、10000以下の最も難しい数を表すこれらの解は、膨大な剰余計算を試行することで作られた総当りらしい解であり、まさにBruteFourFoursと呼ぶのが相応しいだろう。

冪剰余と剰余計算の導入

2015/04/23

10000以下未解決の9353と20000以下未解決の15個を見つけるために、更なる計算手法の拡張を図った。

これまでの計算は一変数演算子と二変数演算子を適用した結果のうち多倍長値28桁に収まるものだけを使っていた。しかし一旦28桁を超える巨大な数が出てきても、次の演算で28桁以内に収まるならまとめて計算できる場合がある。特にそのような計算は、巨大な数を小さな数で割った剰余を求める時に発生する。実際のところ、巨大な数を経由して小さな数に降下可能な演算子は、今許可している四則演算・階乗・累乗・総和・剰余のうち、最後の剰余だけである。

剰余計算の代表的なものとして、冪剰余を考えてみよう。冪剰余とは、AのB乗の結果をCで割った余りを求めるもので、(A^B)%Cだ。例えばこのサイトにある他のスクリプトとして、HugeIntの素数判定では、フェルマーの小定理を計算するために100桁の累乗を100桁の除数で割った余りを求めている。この計算では途中に発生する巨大な累乗を考えずに剰余を求めることができる。計算例として、(2^231)%20195を求めるときは、乗数の231を二進展開して次のように変形する。

(2^231)%20195 = ( (2^128)×(2^64)×(2^32)×(2^4)×(2^2)×(2^1) )%20195

掛け算の剰余は(A*B)%C = ((A%C)*(B%C))%Cに分割して行えるので、2^1を剰余をとりながら二乗し続けていけば、20195未満の二乗計算の繰り返しでこれを計算することができる。

(2^1)%20195 = 2%20195 = 2
(2^2)%20195 = (2^2)%20195 = 4
(2^4)%20195 = (4^2)%20195 = 16
(2^8)%20195 = (16^2)%20195 = 256
(2^16)%20195 = (256^2)%20195 = 4951
(2^32)%20195 = (4951^2)%20195 = 15866
(2^64)%20195 = (15866^2)%20195 = 19476
(2^128)%20195 = (19476^2)%20195 = 12086

( (2^128)×(2^64)×(2^32)×(2^4)×(2^2)×(2^1) )%20195 = 
( 12086×19476×15866×16×4×2 )%20195 = 9353

と解くことができる。これをJavaScriptにすると簡単に書ける。

sHugeInt.powmod = function( n1,n2,n3 ) {
        var Number1 = n1;
        var Number2 = n2;
        var Number3 = n3;
        var binary = Number2;
        var i = new Number();
        
        if(Number1>=Number3)Number1 %= Number3;
        var mod = Number1;
        var Result = ( binary%2 )? mod : 1;
        binary >>= 1;
        
        while(binary>0) {
                mod = (mod*mod)%Number3;
                if( binary%2 )Result = (Result*mod)%Number3;
                binary >>= 1;
        }
        Result %= Number3;
        
        return Result;
}

これを利用すると10000以下で唯一未解決だった9353を解くことができる。

9353 : ((√4)^ΣΣ((Σ(√4))!))%(ΣΣΣ(4!)%ΣΣΣΣ4)

この式は(2^231)%20195である。さっきの例題の冪剰余がこれだ。2^231は真面目に計算すると69桁になり計算出来ない。剰余を含めて計算すれば多倍長どころか通常の数値型に収まる。また次の2つも解ける。

13613 : ((ΣΣ4)^(Σ4)!)%(ΣΣ(4!)-4)
 = (55^3628800)%(45150-4)

18188 : ((√4)^(ΣΣΣ4-Σ((Σ(√4))!)))%ΣΣ(4!)
 = (2^1519)%45150

これで残りは14429,16007,16991,17971,18269,18527,18779,19157,19259,19508,19553,19577,19589になった。では同じような考えで他の未解決部分も解けないだろうか？冪剰余と同じように、巨大な階乗の剰余も階乗を求めることなく解くことができる。すなわち階剰余A!%Bを考えてみよう。

階乗A!をBで割った剰余は、言うまでもなくBはAよりも大きくなくてはいけない。

A!%B = (1×2×3×4....A)%B

この計算は基本的には1〜Aまでの総積を計算しながら、途中で剰余を挟んで有効精度に収めるだけでよい。ただ予め階乗の桁数がわかっていれば、有効精度ぎりぎりまで積を求めて剰余を求めるのが最も効率的だ。A!の桁数はスターリングの公式を使えば求めることができる。そこで先に桁数を求めて、それが有効精度に収まるように積計算を複数の配列に分割して行い、各配列の剰余をとったあとは、その配列の積を順番にとりながら剰余を求めることにする。プログラムは以下のようになる。

sHugeInt.factmod = function(n1,n2) {
        
        var getLen = function(n) {
                return Math.round((n1*Math.log(n1/Math.E)+Math.log(2*Math.PI*n1)/2)/Math.LN10+1);
        }
        
        var len = getLen(n1);
        
        var i;
        var ary = new Array();
        var ary_len = Math.ceil(len/14);
        for(i=0;i<ary_len; i++)ary[i] = 1;
        for(i=1; i<=n1; i++)ary[i%ary_len] *= i;
        var mod = ary[0]%n2;
        for(i=1; i<ary_len; i++)mod = (mod*(ary[i]%n2))%n2;
        return mod;
}

この階剰余により新たに3つが解ける。

19259:√4+(Σ(4!))!%(ΣΣ(4!)-Σ((Σ(√4))!))
 = 2+300!%(45150-21) = 2+ 300!%45129

19508:(ΣΣ((Σ(√4))!))!%(ΣΣΣΣΣ4%(Σ(√4)+ΣΣ(4!)))
 = 231!%(703974775735%(3+45150)) = 231!%(703974775735%45153) = 231!%42013

19553:(ΣΣ4)!%Σ(Σ(√4)+Σ(4!))-ΣΣ4
 = 55!%Σ303-55
 = 12696403353658275925965100847566516959580321051449436762275840000000000000%46056-55

最後の19553は遊びで階乗を展開してみたが、実際の計算ではこの値を直接計算しているわけではないので虚仮威しにすぎない。しかしそれでも、これだけ巨大な数を経由して解けることはこれまでの計算からすれば驚嘆に値する。

これで未解決の問題は残り10個となった。この計算を達成するために改良したスクリプトは4つの4スクリプトver.3.3になる。ただしこのスクリプトは、20000以下の時のような28桁の全範囲での計算は残念ながら重すぎて成功していない。4年前のスクリプトの改良はこれで終了とし、次は冪剰余と階剰余の考え方をより一般化した手法で新しいスクリプトを書き起こしていく。

合同式による計算

2015/04/24

冪剰余や階剰余は剰余計算のアルゴリズムとして有用なものをすくってみただけにすぎない。この計算は四則演算やその他の演算子にも幅広く適用することができ、もっと一般的な剰余、つまり合同式で計算できれば未解決の問題が見つかるかもしれない。

合同式とは自然数同士を割った剰余だけを考える算術のことである。Aをnで割った剰余(mod)をaとするとき、A≡a(mod n)と書き、nをこの合同式の法と呼ぶ。

Aの代わりに剰余aを使って、四則演算が定義できる。同様にB≡b(mod n)とすれば

• 加算:A+B≡a+b(mod n)
• 減算:A-B≡a-b(mod n)
• 乗算:A*B≡a*b(mod n)
• 除算:A/B≡a/b(mod n)　ただしbとnはお互いに素(最大公約数が1)

また合同式では法n内で-aとn-aは等しく、減算の結果が負であっても正として扱える。

これらの演算規則を使って計算していたのが先の冪剰余や階剰余だ。4つの4の演算子のうち、お互いに素という条件のつく除算をここでは扱わないことにすれば、合同式で計算できるのは加減乗算・累乗が無差別に可能で、階乗と総和には一定の制限がある。

階乗は、通常の数字から合同式に新たに加える際にしか計算出来ない。適当な大きさのAについてA!≡c(mod n)を計算したとしても(A!)!≡c!(mod n)とは書けない。A!＞nならば(A!)!≡0(mod n)になるので、剰余の計算にはA!を知る必要がある。

総和はnが奇数の場合だけ半無限に合同式内で実行できる。ΣA=A(A+1)/2≡c(mod n)を計算するには、ΣA=(1+2+3+4+5....A)と展開すれば1〜Aまでの加算は周期nで繰り返すだけになる。つまり(1+2+3...n +1+2+3...n +1+2...)になり、Aをnで割った商を[A/n]とすると

ΣA≡[A/n]Σn+Σa (mod n)

Σnをnで割った余りはnが奇数か偶数かによって変わる。

• nが奇数:Σn=n(n+1)/2≡0*(n+1)/2≡0(mod n)
• nが偶数:Σn=n(n+1)/2≡n/2(mod n)

nが奇数の場合のみ、Σnの剰余は0が保証される。したがって

• nが奇数:ΣA≡Σa (mod n)
• nが偶数:ΣA≡[A/n]n/2+Σa (mod n)

となり、nが奇数の場合のみ合同式内で完結する。nが偶数の場合は、合同式の外部から加える際に1回だけしか計算出来ない。結果的には、奇数の法nによる総和計算が型破りに強力となった。

//f1
singleN(1);

//f2
doubleN(1,1,2);
singleN(2);

//f3
doubleN(1,2,3);
singleN(3);

//f4
doubleN(1,3,4);
doubleN(2,2,4);
singleN(4)

//f1 
singleN(1);

//f2
singleM(1,2,1);
doubleN(1,1,2);
singleN(2);

//f3
doubleM(1,1,2,1);
singleM(2,3,1);
singleM(1,3,2);
doubleN(1,2,3);
singleN(3);

//f4
doubleM(1,2,3,1);
doubleM(1,1,2,2);
singleM(2,4,2);
singleM(1,4,3);
doubleN(1,3,4);
doubleN(2,2,4);
singleN(4);

14429 : ((ΣΣΣΣΣΣΣΣ(((Σ(√4))!)!))^(4!)!)%Σ(Σ(4!)-√4)
16007 : (√4+ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ4)%((ΣΣ4)^Σ(√4))
16991 : (ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ((Σ(√4))!)-((Σ(√4))!)!)%ΣΣ(Σ((Σ(√4))!)-√4)
17971 : ((ΣΣ((Σ(√4))!))^(Σ4)!)%Σ(4+ΣΣ((Σ(√4))!))
18269 : (Σ((Σ(√4))!)-(Σ4)^(Σ(√4))!)%ΣΣΣ((Σ(√4))!)
18527 : ΣΣΣΣΣΣΣΣΣΣΣ(4!)%(ΣΣΣ((Σ(√4))!)-(4!+ΣΣ4))
18779 : (ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ(((Σ(√4))!)!)-ΣΣΣΣ((Σ(√4))!))%(ΣΣ4+ΣΣ(4!))
19157 : Σ(ΣΣΣΣΣΣ(((Σ(√4))!)!)*Σ(((Σ(√4))!)!))%Σ(Σ(4!)-√4)
19577 : ΣΣΣΣΣ(((Σ(√4))!)!)%Σ(Σ(4!)-√4)-4!
19589 : ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ(4!)%(ΣΣ4+Σ(4^4))

19409 : ΣΣ(ΣΣ4+ΣΣ((Σ(√4))!))%ΣΣ(4!)-√4

19409 : 
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ
ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ((Σ(√4))!)%((Σ(√4))^Σ4)-ΣΣΣ4

18269 : ΣΣΣΣΣΣΣΣΣΣΣΣΣΣΣ(4!)%(ΣΣ4+ΣΣΣ((Σ(√4))!)-√4)

((Σ(√4))^Σ4) = 3^10 = 59049

任意の自然数の完全解決へ

2015/04/26

法59049のときΣΣ....ΣΣ2%59049がΣを13122回増やすまで値がループしないことがわかったが、ここから一般の場合で解けないかを考えてみよう。任意の59049未満の自然数を次の式で表すことは可能か？

({Σ^p}f(4)+{Σ^q}g(4))%((Σ(√4))^Σ4)
({Σ^p}f(4)-{Σ^q}g(4))%((Σ(√4))^Σ4)
({Σ^p}f(4)*{Σ^q}g(4))%((Σ(√4))^Σ4)

Σ^pとΣ^qはΣをp回,q回繰り返したことを意味し、f(4)とg(4)は1つの4で作れる候補を表す。答えは可能、59049未満の全ての解。

では今度は、59049より大きな値で59049のような長い周期を持つものはないだろうか？計算するとスクリプトの有効精度に収まる94906265以下では、1つだけ見つかる。

531441:√((Σ(√4))^4!)=3^12

531441の周期は118098で、最長の周期を持つ数は59049と同じ2のときだ。ここで2つのことに気づく。59049も531441も3の乗数であること。それぞれの数を周期で割った値はぴったり2/9になることだ。ここで、Σ...Σ2%3^10とΣ...Σ2%3^12が表現できる数を調べてみると、興味深いことがわかる。作成できる数は

3,6,12,15,21,24,30... 9m+3,9m+6

となるのだ。つまり3の倍数のうち9の倍数を除いた数全てを網羅する。もし法3^nでΣ...Σ2の剰余が3^n未満の9m+3,9m+6になるならば、この剰余系で4つの4の一般解を求められる。もし9m+3と9m+6が揃うとしたら、全ての自然数を作る式は以下のようになる。

9n : 9m+3 - Σ(√4)
9n+1 : 9m+3 - √4
9n+2 : 9m+6 - 4
9n+3 : 9m+6 - Σ(√4)
9n+4 : 9m+6 - √4
9n+5 : 9m+3 + √4
9n+6 : 9m+3 + Σ(√4)
9n+7 : 9m+3 + 4
9n+8 : 9m+6 + √4

一般解:({Σ^p}√4)%(Σ(√4)^f(4))±g(4)
f(4):1つの4でできる自然数
g(4)=4,√4,Σ(√4)

すでに見つかっている59049はもちろん531441にも該当するので、少なくとも531440以下の4つの4も解決した。そして、任意の自然数で4つの4が完全解決するためには「(Σ...Σ2)%3^nが3^n未満の3の倍数かつ9の倍数ではない自然数を全て巡回する」こと証明できればよい。