Archives program　JavaScriptによる4つの4

概要

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オブジェクトの内部に作成した。その上で、個々の動作について簡単に説明する。

演算オブジェクト

4つの4は、4を4個使って数式を作るものだ。数式を扱いやすいように、数式とその値を格納する演算オブジェクトを作った。

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

演算オブジェクト、NumCmbFF.Formuは3つの変数を持つ。

valueはその数式の計算結果の数値を持つ。

formulaはその数式の形を持つ。形式は文字列で、一変数演算子は["演算子名",変数1]、二変数演算子は["演算子名",変数1,変数2]で、入力される変数も全く同様の数式の形式を持ち、それらの入れ子構造になっている。これを文字列で格納しておき、最後に読める数式の形に変換する。

complexは数式の複雑さを表す。演算子ごとに複雑さの数値を設定し、演算子を作用させるたびに数値が増えていく。全く同じ結果になる数式や、無駄な演算子を繰り返しただけの数式を消去するため、最も値の小さな結果のみを残して消去されるようにする。

演算オブジェクト同士の演算

例として加算を挙げる。

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;
}

演算オブジェクトを引数とした各演算子の関数があり、ここにオブジェクトを渡すことで計算結果の演算オブジェクトを得る。

演算オブジェクトから数式への変換

formulaの文字列形式は、そのままスクリプトと認識させると多次元配列に変換されるようになっている。この多次元配列データから読みやすい数式に翻訳する。コードは煩雑なのでここには記載しない。

演算オブジェクトの格納方式と探査関数群

演算オブジェクトは4の使用回数毎に、1回、2回、3回、4回の4つの配列に格納する。初期値には4,44,444を入れている。

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

この配列を操作する関数は大きく3つある。中身の具体的なコードは複雑なのでここには挙げない。

NumCmbFF.s.singleS

引数には格納配列listの番号を指定し、指定された番号の配列内の演算オブジェクトに、設定されている回数だけ一変数演算子を適用する。ただし範囲制限の外にはみ出した適用結果は無視されリストに追加されない。

NumCmbFF.s.doubleS

引数には格納配列listの番号として、入力2つと出力1つの3つを指定し、2つの入力リストを変数とした二変数演算子を作用させ、3つ目のリストに出力する。singleSと同じく範囲制限の外にはみ出した適用結果は無視されリストに追加されない。

NumCmbFF.s.classifyAry

引数には格納配列listの番号を指定し、リスト内にある演算オブジェクトのうち、同じ値を持つものを、最も複雑さの小さいものを除いて全て消去する。この処理を実行するとリスト内にあるオブジェクトの数値は異なるものが1つずつだけになる。

4つの4問題の実行

3つの関数が揃えば、4つの4問題を実行するのは簡単だ。作用は4の使用回数を考え、1+1=2,1+2=3,1+3=4,2+2=4の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);

最後に、4つすべてを使った配列から、複雑さの最も低い自然数を抜き出せば解の一覧を得ることができる。

作成した計算スクリプト

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個区切りでテキストエリアに出力される。

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

得られた答えについて

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 = \frac{4! \times 4! - 4!}{4}

138:分子が全て階乗。

159 = Σ Σ 4 + 4 \times (\sqrt{4} + 4!)

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

162 = {(\sqrt{\sqrt{\sqrt{4}}} + \sqrt{(\sqrt{\sqrt{4}} \times 4)})}^{4}

162:平方根の3重式。

210 = \frac{(\frac{4 + 4!}{4})!}{4!}

210:階乗式の多重分数。

511 = \frac{{\sqrt{4}}^{\sum 4} - \sqrt{4}}{\sqrt{4}}

511:平方根ばかりの式。

767 = \frac{\sum \sum \sum 4 - (\sqrt{4} + 4)}{\sqrt{4}}

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

5000以下の計算結果

2011/03/19

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

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

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

3613 = \frac{4! + \frac{\sum (((\sum \sqrt{4})!)!)}{4!}}{\sum \sqrt{4}}

3707 = (\sum (((\sum \sqrt{4})!)!) - \sum \sqrt{4}) % \frac{\sum \sum (4!)}{\sum \sqrt{4}}

3857 = \frac{\sum \frac{\sum \sum \sum 4}{\sqrt{4}}}{\sum \sum 4} - \sum \sum \sum 4

3887 = \frac{\sqrt{{((\sum \sqrt{4})!)}^{\sum 4}} - \sqrt{4}}{\sqrt{4}}

3989 = \frac{\sum \sum \sum \sum ((\sum \sqrt{4})!) % (\sum (((\sum \sqrt{4})!)!) - \sum ((\sum \sqrt{4})!))}{\sum ((\sum \sqrt{4})!)}

4273 = \sum \sum \sum (4!) % (4 + 4! \times \sum (4!))

JavaScriptによる4つの4 - FourFours

概要

プログラムの動作概要

演算オブジェクト

演算オブジェクト同士の演算

演算オブジェクトから数式への変換

演算オブジェクトの格納方式と探査関数群

NumCmbFF.s.singleS

NumCmbFF.s.doubleS

NumCmbFF.s.classifyAry

4つの4問題の実行

作成した計算スクリプト

得られた答えについて

5000以下の計算結果

ページ情報