JavaScriptによる4つの4 - FourFours

概要

2011/03/19

数字の4を4つ使った組み合わせで任意の自然数を作る有名なゲーム、4つの4(FourFours)について、JavaScriptを用いて可能な限り高速に答えを自動生成させるスクリプトの開発を試みた。

元となっているのはJavaScriptによる4つの数字ゲームのときに作ったコードで、これを簡略化、更に最適化を施した。元となった4つの数字よりも格段に優れたものになった。

このページでは現在、1000以下の自然数を1秒以内(GoogleChromeでの測定、IE8では10秒程度を要する)に求めることに成功し、更に2個を除いて5000以下のほとんど全ての自然数についての解を得ることに成功している。

(2015/04/20)続編ができた。

プログラムの動作概要

2011/03/19

全コードはNumCmbFFオブジェクトの内部に作成した。その上で、個々の動作について簡単に説明する。

NumCmbFF.Formu = function(val,comp)
{
        this.value = parseInt(val);
        this.formula = '["none",'+val+']';
        this.complex = (comp)? comp : 0;
}

NumCmbFF.Formu.add = function(obj1,obj2)
{
        var res = new NumCmbFF.Formu();
        res.value = obj1.value+obj2.value;
        res.formula = '["add",'+obj1.formula+","+obj2.formula+']';
        res.complex = obj1.complex+obj2.complex+NumCmbFF.Formu.v.comps[0][0];
        return res;
}

NumCmbFF.v.list = new Array();
NumCmbFF.v.list[0] = [new NumCmbFF.Formu(num)]//1
NumCmbFF.v.list[1] = [new NumCmbFF.Formu(num*11,1)]//2
NumCmbFF.v.list[2] = [new NumCmbFF.Formu(num*111,2)]//3
NumCmbFF.v.list[3] = []//4

        //一変数演算子の適用
        NumCmbFF.s.singleS(0);
        NumCmbFF.s.classifyAry(0);
        
        /* ----------第2項---------- */
        //二変数演算子の適用
        NumCmbFF.s.doubleS(0,0,1);
        NumCmbFF.s.classifyAry(1);
        //一変数演算子の適用
        NumCmbFF.s.singleS(1);
        NumCmbFF.s.classifyAry(1);
        
        /* ----------第3項---------- */
        //二変数演算子の適用
        NumCmbFF.s.doubleS(0,1,2);
        NumCmbFF.s.classifyAry(2);
        //一変数演算子の適用
        NumCmbFF.s.singleS(2);
        NumCmbFF.s.classifyAry(2);
        
        /* ----------第4項---------- */
        //二変数演算子の適用
        NumCmbFF.s.doubleS(0,2,3);
        NumCmbFF.s.classifyAry(3);
        NumCmbFF.s.doubleS(1,1,3);
        NumCmbFF.s.classifyAry(3);
        //一変数演算子の適用
        NumCmbFF.s.singleS(3);

作成した計算スクリプト

2011/03/19

• JavaScriptによる4つの4 ver.2.1

ツールは初期設定で実行すると、手元の環境ではGoogleChromeを使うと0.5秒程度で1〜1000までの解を得ることに成功している。設定箇所が多いので、各項目について簡単に説明しておく。何れの項目もいたずらに値を増やすと計算が終了せずブラウザが応答しなくなる可能性があるので、注意を要する。

材料にする数字

1桁の自然数を1個指定する。4つの4ということで4が入力されているが、他の数字を使っても構わない。

検索する範囲

検索範囲を指定する。指定された範囲の結果が出力されるようになる。ただし、基本的に組み合わせをすべて計算するため、範囲を狭くすれば計算量が減るというものではない。

許可する演算子

許可する演算子の種類を指定できる。四則演算は固定、それ以外はチェックボックスから指定可能。階乗のみ計算する上限をつけることができる。複雑性は演算子を作用させたときに増えるcomplex値となっている。値が大きいほど、その演算子は使われにくくなる。

各項の一変数演算子の多重度上限

一変数演算子の作用はNumCmbFF.s.singleS関数1回で実行される。このとき、各格納リストで一変数演算子を連続何回作用させられるかを指定できる。初期値の3-1-1-1では、4単体には3回、4を2回以上組み合わせた数式には1回ずつしか適用されない。値が大きいほど探査範囲は大きくなるが、同時に計算量も増える。

小数の途中結果を無視(入力値倍して小数のものを無視、0:小数許可,1:整数のみ)

計算結果が小数点を含む時、その結果を捨てるかどうかを指定する。1で整数だけ。0では全ての小数を許可。自然数を指定した場合、その値を掛けた結果が自然数のときだけ採用する。例えば4を入力すると、1/2や1/4は捨てずに採用される。殆どの場合小数を捨てても結果は変わらない。

無理数となる平方根を無視

平方根を作用させたときに無理数のデータが得られたとき、値を捨てるかどうかを指定する。捨てなければより大きな範囲を探索できるが、無理数から再び自然数に戻る例は極めて稀で、捨てても一部の特殊な解を除き問題はない。捨てなければ計算量は激増する。

大きな値を無視(入力値より大きな値を無視、探査範囲以上を指定,0:無制限)

計算結果が大きくなりすぎた場合に値を捨てるかどうかを指定する。上限値を入力、0で無限大だが、計算精度は有限なので2^53=9007199254740992以上は意味がなく、精度が落ちる危険がある。よって0指定は推奨しない。尚、負の値は全く意味がないため強制的に捨てられる。

表示方法(発見済みのみ詰め表示 or 未発見の箇所を空白表示)

出力結果の一覧表について、未発見の箇所を無視して発見済みの解を小さい順に並べるか、未発見箇所をNot Findとして空白にするかを指定できる。出力は500個区切りでテキストエリアに出力される。

また製作途中の古い物を幾つか残してあるので、リンクしておく。

• numcombFF0
• numcombFF1

得られた答えについて

2011/03/19

スクリプトの結果を使って、1から100までの作り方について吟味してみた。ここでは小数点や小循環小数を一切考えていないので、それらを用いればより簡単に構成できる可能性がある。他の演算子については今後検討を予定している。

1から順調に始めて、18までは四則演算・(累乗)・平方根だけで構成できる。

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 : 4+4-4/4
8 : 4+4+4-4
9 : 4+4+4/4
10 : (44-4)/4
11 : 44/√(4*4)
12 : 4*(4-4/4)
13 : √4+44/4
14 : √4+4+4+4
15 : 4*4-4/4
16 : 4+4+4+4
17 : 4/4+4*4
18 : 4-√4+4*4

しかし、これだけでは19は作れない。19を作るには1〜nまでの自然数を全てかけ合わせる階乗!が必要になる。4!=1*2*3*4=24だ。この調子で38まで作ることができる。

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)

中でも33は面白い。33は平方根を3度使用して4の8乗根を得、これを4!乗することで4^3を得ている。(4^3+2)/2=32+1=33だ。

39以上はさらに総和を使用する必要がある。Σnと書いて、1〜nまでの自然数を全て足した数を意味する。Σ4=1+2+3+4=10、というふうに。Σの使用を許可すると、一気に100まで作ることができる。それどころか、1000まで全て作ることができてしまう。1000までの答えは、計算スクリプトの初期設定で計算すれば直ぐに答えを見ることができる。

39 : 4*Σ4-4/4
40 : 4*(√4+4+4)
41 : 4/4+4*Σ4
42 : √4+44-4
43 : 44-4/4
44 : 4+44-4
45 : 4/4+44
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+4)-√4
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 : 4+Σ(4!)/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 : 4*4!-4/4
96 : 4!*(4+4-4)
97 : 4/4+4*4!
98 : 4-√4+4*4!
99 : (√(Σ4))^4-4/4
100 : 4*(4!+4/4)

1000未満で面白い解を幾つか抜粋。

138:分子が全て階乗。

159:初めて出現するΣ2重式。

162:平方根の3重式。

210:階乗式の多重分数。

511:平方根ばかりの式。

767:初めて出現するΣの3重式。

5000以下の計算結果

2011/03/19

• 4つの4(FourFours)問題　5000以下の解 by JavaScript

作成したスクリプトで広い範囲を調べた結果を掲載。5000以下を対象にできるだけ広い範囲で調べた結果、上記ページのような結果を得た。全リストはページ参照。

小数点をカットし、上限値がそこそこの値では5000以下の答えのうち、4992個までは簡単に見つけることができる。残り8個のうち2個の作り方は現時点では不明で、さらに範囲を広げて見つけた6つの式は、4つの4の中でも飛び抜けて難解で巨大な数を経由するものだ。その6つの数式表現を並べておく。動作概要にあった3つの関数の動作だけで、これほど複雑な数式まで踏み込むことができた。