6 : 04 四則演算でYを作るのに必要なXの最小個数

2016年は平成28年だが、整数 28 と四則演算の組み合わせで 2016 を表すためには、最小でも9個の 28 が必要だ。例えば:

どうして「9個が最小」と分かるのか？　「8個以下ではできない」ことは、どのように示されるか？

全数検索で解くのは困難なようにも思えるが、この種のパズルは、50～100行程度のシンプルなコードにより高速に解決される。

以下ではそのアルゴリズムを紹介し、JavaScript による実装例を示す。実験として ES6 (ECMAScript 2015) の Map と Set も試した。Map は従来のマップ風 Object とほぼ同じ機能を持つが、数値をキーとする場合には効果が高い。おまけとして「組み込み関数の splice より速い配列への要素挿入法」も紹介。

パズル自体は面白いだけで何の役にも立たないが、アプローチの中には応用の利く事柄もあるかもしれない。

[1/7] パズルの内容

「2828も2個の28だ」と見なすなら、次のように、この数は5個まで減らせる。

• 2016 = 2828−(28×28+28)

「反復による桁増やし・べき乗・平方根などを許容するかしないか」のルール設定により、一般に解（必要となる最小個数）は異なる。最初は「純粋に四則演算のみ使用可。数を並べて桁数を増やすのは駄目」というシンプルなルールでいこう。

27 を使って 2015 を作る場合、最小でも13個の 27 が必要になる。例えば:

問題は次の形に一般化される。

• 1以上の任意の整数 X と Y が与えられたとき、次の条件を満たす最小の自然数 h を決定せよ。
  • 条件「h 個の X、h−1 個の二項演算子、0対以上の括弧を組み合わせて、値が Y に等しい式を作ることができる」

簡単に言えば:

• X と四則演算の組み合わせだけで Y を作りたい。最小何個の X で可能か？

「西暦・平成型」は、X = Y−1988 とした特別な場合に当たる。もっと一般の場合の例として、2016 は7個の 4 で表現される。

• 2016 = (4×4×4×4−4)×(4+4)

指数を許せば、5個の 4 で表現されるが、今は四則演算に限っている。

• 2016 = (4⁴−4)×(4+4)

以下では、この種の問題における必要な X の最小個数を決定することを考え、そのためのアルゴリズム例を紹介する。

「任意」だと具体的に試しにくいので、一応「X と Y は、どちらも1～5000の範囲」としておく。

[2/7] アルゴリズムのスケッチ

28 を使って 2016 を作りたいとする。

今、箱が幾つもあって、箱1・箱2…と番号が振ってあるとする。

箱1には、28 を1個使って作れる数を格納する。それは 28 自身に他ならない。

箱2には、「箱1の任意の数と箱1の任意の数に四則演算を施したもの」を格納する。任意といっても箱1には 28 しか入っていないのだから、結果は 28+28=56, 28−28=0, 28×28=784, 28/28=1 の4個に限られる。

箱3には、「箱1の任意の数と箱2の任意の数に四則演算を施したもの」を格納する。

箱4には、「箱1の任意の数と箱3の任意の数に四則演算を施したもの」と「箱2の任意の数と箱2の任意の数に四則演算を施したもの」を格納する。

以下同様に進んで、だんだん大きい番号の箱を埋めていく。どこかで 2016 が現れれば、そのときの箱の番号が求める答え。

要するに、n 個の 28 で作れる数の集合は有限であり、その要素は整然と列挙される。

[3/7] バージョン1

主要部分（14行）

「アルゴリズムのスケッチ」の内容を JavaScript で書くと、骨格は次のようになる。1番の箱、2番の箱…が順に作られ（最大29番まで）、どこかの箱に Y が入っていたら、その箱の番号 n が報告される。

var X = 28;
var Y = 2016;
Search();

function Search()
{
    var box = []; // box array

    for( var n = 1; n < 30; ++n ) {
        Make_new_box( box, n ); // box[0] is unused

        if( box[ n ][ Y ] ) {
            alert( n );
            break;
        }
    }
}

ミックスによる箱の構築（28行）

「新しい箱を作る」という部分では、1番の箱には X をそのまま格納し、2番以降の箱には「既存の箱の中身をミックスして作った数」を格納する。箱Aと箱Bを「ミックスする」ということは、Aの中身（箱Aに入っている数）のそれぞれと、Bの中身のそれぞれとの間で四則演算を行い、生じた数を保存することだ。

function Make_new_box( box, n ) // n: box number
{
    box[ n ] = {}; // Object, used as a map

    if( n == 1 ) {
        Store( X, box, 1 );
    } else {
        for( var i = 1; i <= n/2; ++i )
            Mix( box[i], box[n-i], box, n );
    }
}

function Mix( boxA, boxB, box, n )
{
    for( var a in boxA ) {
        for( var b in boxB ) {
            Calc( a, b, box, n );
        }
    }
}

function Calc( a, b, box, n )
{
    a = Number(a);
    b = Number(b);

    if( a < b ) { var tmp = a; a = b; b = tmp; }

    Store( a + b, box, n );
    Store( a - b, box, n );
    Store( a * b, box, n );
    if( b != 0 && a % b == 0 ) Store( a / b, box, n );
}

Calc に渡される a と b は、このバージョンにおいては「連想配列のキー」として実装されている。JavaScript においては（このコード例においては）、これは Object のプロパティー名であり、文字列である。数値型に変換しないと、足し算が文字列の連結になってしまうので注意。

このとき、箱Aから出した数 a と箱Bから出した数 b について、もし a が b より小さいときは最初に a と b をスワップしておく。スワップしても足し算・掛け算の結果は変わらないが、

• 引き算については、スワップの結果、負数が発生しなくなり、マイナスにならない方向に引き算した結果だけが保存されることになる。実際、マイナスの数経由で Y を作れるなら、計算の順序を適当に入れ替えれば、マイナスの数を経由しないでも Y を作れる。
• 同様に、割り算については、割り切れる場合だけ考えれば足りる。実際、割り切れない分数に後から大きな数 Z を掛けて整数 Y を作れたとすると、最初の分数の分子に先に Z を掛けて分母で割れば、整数演算だけで同じ結果が得られる。[追記: 厳密に考えると、この主張は微妙？]

これらは演算の順序だけの違いなので、「X を何個使っているか」という本筋には影響しない。

このようにしないと、生成できる数の個数が増えてメモリーが浪費され、計算量が増大して検索が遅くなる上、割り切れない数が絡む計算については丸め誤差に悩まされることになるだろう。

生成された数を格納（7行）

生成された数を作成中の箱にどんどん詰めればいいのだが、「既存の箱のどれかに入っている数（もっと少ない個数の X で作れる数）については重複して新しい箱に入れることはしない」と約束しておく。

function Store( number, box, n )
{
    for( var i = 1; i < n; ++i ) {
        if( box[ i ][ number ] ) return;
    }

    box[ n ][ number ] = true;
}

箱の一つ一つは Object であり、その Object が持つプロパティーが「マップ（連想配列）のキー」の役割を果たす。number を箱 n に入れるということは、

• box[n][number] というキーが作られ、
• そのキーに対する値が true に設定される

ということだ。一方、その箱に入っていない数についてはキーが未定義となり、未定義値をブールに変換すれば false なので、事実上、box[n][c] は、「数 c が箱 n に入っている」という命題の真偽を表す。（JavaScript では配列とオブジェクトが同じように表現可能なため、上記は2次元配列のように見えるが、本物の2次元配列ではない。）

「その数を箱 n に入れるかどうか」の判定において、ここでは「その数が箱 n 自身に既に入っているか」のチェックはしていない。もし既に入っていても、構わず同じキーと値のペアが再格納される（結果的に箱の中身は変化しない）。

バージョン1の結果報告

以上、空行を除けば、合計49行の簡単なスクリプトだが、これを実行すると、めでたく 9 という答えが、それも0.1秒未満で得られた。

この例はたまたま h = 9 と解が小さいので良かったが、一般には、このままでは速度的に問題がある。例えば27を使って2015を作る場合 h = 13 だが、バージョン1を使ってそれを求めると、テスト環境では約6秒もかかってしまった。h = 16 や h = 17 になることもあるのに、h = 13 の検索がこれでは困る。

とりあえず動くことは分かったので、さっそく高速化にかかろう！

[4/7] 高速化その1

高速化には「数学的な考察によって、実装すべき処理を改善する＝無駄な仕事を引き受けない」という面と、「プログラミング的な工夫によって、処理を改善する＝引き受けた仕事の効率を上げる」という面がある。この章では前者を扱う。

上界の評価

バージョン1で「13個の27で2015」の検索をすると、箱12以降において中身の最大値が2の53乗以上になり、JavaScript で正しく扱える整数値の限界 2⁵³−1 を超えてしまう。要素数も箱12で10万個以上、箱13で30万個以上。これでは計算量が大きいのも当然で、計算精度も問題になる。

大きな数を無制限に保存しても仕方ない。「13個の27で2015を作る」という例でいうと、箱13には、もちろん 2015 より大きい数は必要なく、箱12には、(2015×27)+1 以上の数は必要ない。実際、数を小さくする最強の方法は割り算だが、(2015×27)+1 以上の数を 27 で割っても（そして割り切れたとしても）ターゲットの 2015 より大きい数しか得られない。つまり、そのような数を経由してパズルが解ける可能性はない。同様に考えて、箱11には、(2015×27²)+1 以上の数は必要ない（四則演算のみという今回の前提においては）。

この考えを一般化すると: 解に関係する可能性がある最大の数は、最後の箱の k 個前の箱において、

• YX^k

である。すなわち、h 個の X で Y を作れるとき、箱 n において、

• YX^h−n 「あ」

より大きな数は、解に関係しない。箱を作るとき、これより大きい数を無視することにしよう。

上記の数を表す変数 MaxLimit を設定し、Store の最初で MaxLimit を超える数を弾くようにすると、箱に格納される要素の個数が激減し、計算量が桁違いに減って処理が速くなる。

上界をきちんと考慮した上で全数検索し、例えば h = 13 という解が得られた場合、基本的にそれは厳密解であり、「12個以下にはできない」ということが証明される。

2パス方式

上記の MaxLimit の設定では「使用する X の合計個数 h」を用いているが、パズルを解かない限り h が幾つなのか分からない。「解を得るための補助パラメーター」として「解が出てからでないと分からない h」を利用するのでは、循環論法になってしまう。

この場合、最初の試行（簡易検索）では、MaxLimit を暫定的に 2²⁴ に固定しておくといい。現実には 2²⁴ より大きい数を経由して Y が生成されることもあるが、簡易検索では（速度を優先するために）その可能性を無視する。この制限の下で「X が h 個必要」という解（近似解）が得られたとき、今度はその h を使って MaxLimit を設定し全数検索を行う。ほとんどの場合、最初と同じ結果が得られるが、2回目の結果は厳密解となる。

正確に言えば、2パス目では、h ではなく h−1 を使うことができる。実際、1パス目で「それが最小かは分からないが、とりあえず h 個あればできる」ことが分かったとして、2パス目で「h−1 個以下ではできない」ことが分かれば、h が最小（すなわち求める解）であることが証明される。条件によっては、2パス目において「h−1 個以下の X で Y を作る方法」が発見される可能性もあるが、その場合、その個数が「全数検索による解」となる。（「あ」から明らかなように、同一番号の箱において、大きな h に対する上界は、小さな h に対する上界を兼ねている。）

ただし、MaxLimit が 2⁵³ 以上になって、計算に 2⁵³ 以上の数が現れた場合、そのままでは、この「厳密解」には理論上の傷が残る。

高速化その1の結果

「13個の27で2015」の計算時間はバージョン1では約6秒だったが、約3秒（簡易検索2.8秒、検証0.2秒）に改善された。しかし、もっと大きな解を扱うことを考えると、まだまだ遅過ぎる。例えば「16個の91で2079」は、簡易検索20秒、検証3秒を要する。

[5/7] 高速化その2

マップ検索の高速化

バージョン1のまずい点は、Store において、ある数が既存か新規か判定するために、既存の全部の箱の中を調べていること。箱の中はマップであり、キーの有無を検索するだけでも少し時間がかかる。一つの数を検討するごとに毎回毎回幾つものマップを調べるのは、できれば避けたい。

そこで、グローバル・オブジェクトとして「どれかの箱に入っている数は全部記録してある」というデータベース DB を作り、既存か新規かの判定はそこへの1回の問い合わせだけで完了するようにしよう。これによって、Store は「作成中の箱番号」を知る必要もなくなり、Mix 以降、「箱の配列と箱番号」を渡す代わりに、単に「作成中の箱」（を表す何らかの参照）を渡せば足りることになる。

同じキーが箱と DB の2カ所に作られるためメモリー使用量はざっと2倍になってしまうが、これだけで（他の最適化とは独立に）4～6倍程度の高速化が実現される。後述するように、DB をマップとする一方、箱は配列にして使い分ければ、2通り保持することがむしろメリットとなる。

打ち切りによる高速化

一般に、箱の番号が増えるほど、箱の生成に必要な計算量は増大する。箱の番号が1増えるごとに、計算量はざっと2倍になるようだ。当然ながら、計算終了時点の最後の箱は、生成に一番時間がかかる。h が全く分からない状態での最初の試行では、箱そのものも巨大になる。

h が定義され、MaxLimit による制限が厳格になった場合、最後の箱には Y 以下の数だけが入るので、箱のサイズは劇的に小さくなるが、これは見掛け上 Y より大きい数がフィルターされているだけで、背後で行われている計算は必ずしも劇的には減っていない。むしろ一般には、h が定義されると中間の箱のサイズが増加し、それを経由した最後の箱の生成についても計算量が増える。

どちらの場合についても、ここに高速化の余地がある。すなわち、h の最小値を決定するのが目的なら、1個でも Y が生成されたとたん、そこで計算を中止して構わない。さらに計算を進めた場合、「同じ個数の X で Y を作れるもっときれいな式」が見つかる可能性はあるものの、X の個数 h は小さくならないからだ。

このメカニズムを実現するためには、Calc などの関数が値を返すようにして呼び出し側で戻り値をチェックするか、または、DB[Y] が定義されたかどうか頻繁にチェックすればいい。しかし、後者の方法はマップ検索なので効率が悪い。生成された数が直接見える Store において、Y を格納したら true を返し、呼び出し側はこれをトリガーに検索を打ち切るのがいい。これだけで、平均2倍近く速くなる。

要するに、一つの箱を完成させてから「中に Y が入っていないかな」と探すのではなく、箱を作っているとき箱に入れる数を常に監視し、Y を箱に入れたとたんそれに気付くようにする。

箱を構築する部分の高速化

バージョン1の Make_new_box には、高速化の余地がある。

明白な問題点として、A と B が同一の箱の場合、Mix をそのまま呼ぶと、全く同じ四則演算がざっと2回ずつ実行されてしまう。例えば、{x, y, z} の3要素を含む箱を自分自身とミックスすると、四則演算を # として、x#x, x#y, x#z, y#x, y#y, y#z, z#x, z#y, z#z が実行されるが、第1項と第2項は大きい順に並べ替えられるため、x#y と y#x などは全く同じ意味であり、同じことを2回やるのは無駄だ。要素数が1000だとすると、Mix では100万回の Calc が必要になるが、重複を省いて、ざっと半分の回数で済ませたい。箱を自分自身とミックスする場合、箱の中身を並べたキーの配列を作り、インデックスにより範囲を絞って無駄な演算の重複をなくすべきだろう。それを行う Self_mix を導入して呼び分けると、それだけでかなりの高速化になる。

どうせそこで配列が必要になるのなら、最初から箱の中身を配列にしておこう！

例えば box[12][100] は、バージョン1では「箱12に数100が入っているという命題の真偽」と等価だったが、バージョン2では「箱12に入っている100番目（ソートされていない）の数」となる。外部にデータベースを作ったので、箱には「既存・新規の判定」の仕組みは必要ない。

これで速度が上がる理由の一つは、（一般的に言って）配列のイテレーションの方がマップのキーのイテレーションより速いことだ。しかし、もっと根本的な理由として、配列なら数値を出し入れできるが、Object のキーは基本的に文字列ということがある。数値と文字列の相互変換は遅い上、数値を文字列として保持するとメモリーが無駄になり、受け渡しの効率も悪いのだろう。

では、いっそのこと DB も配列にして、DB.push() で数を格納してはどうか？　その検討については、付録参照。

魔チューン

簡易検索において箱の番号が16以上になったとき、MaxLimit を 2¹⁶ に下げると速度が改善される。根拠は「想定している数の範囲では、ほとんどの場合、最大でも16個（まれに17個）の X があれば、Y を作れる」という経験則。ただし、あまり絞ると、簡易検索の結果が過大になる可能性が上がる。過大な h をなるべく防ぎたい場合、

• MaxLimit の値を箱16では 2²⁰、箱17以降で 2¹⁶ にする 「い」

という方法もある。バージョン2では、このチューンを使う。

これが最善というわけではなく、簡易検索における MaxLimit はもっと小さくすることもできるはずだ。

15個以内の X で Y を作れる場合、このチューンには効果がないが、害もない。

[6/7] バージョン2

上記のアイデアを織り込みながら、各部を更新してみた。

主要部分（38行）

f53 フラグについては後述。

Search(x,y,nBox) を呼ぶと、「nBox 個以下の x を使って y を作る方法」が全数検索される。第3引数を略して Search(x,y) を呼ぶと、簡易検索が実行される。いずれの場合も、y を作れたら直ちに検索が打ち切られ、そのときの（中に y が入っている）箱の番号が answer に格納される。関数は answer を返す（answer を決定できなかった場合は 0 を返す）。

var DB; // database
var MaxLimit = 16777216; // 2^24 (default)
var Y;
var f53 = false;
var MAX_X=5000, MAX_Y=5000, MAX_NBOX=29, DEF_NBOX=29;

var answer = Search( 27, 2015 ); // answer=13 (estimated)
/// answer = Search( 27, 2015, 13 ); // answer=13 (proven)

function Search( x, y, nBox ) // nBox: max number of boxes
{
    if( ! Is_valid( x, y, nBox ) ) return 0;

    DB = {};
    Y = y;
    var box = new Array( ( nBox ? nBox : DEF_NBOX ) + 1 );

    var answer; // Y is in box[answer]
    for( var n = 1, len = box.length; n < len; ++n ) // box[0] is unused
    {
        MaxLimit = Get_upper_bound( x, y, nBox, n );

        if( Find_Y_in( box, n, x ) ) {
            answer = n;
            break;
        }
    }
    box.length = 0; // *1
    Show_results( x, y, answer, nBox ); // *2
    DB = void 0; // *3

    return (answer || 0);
}

nBox は、使う箱の最大個数で、box 配列の長さは、それより 1 大きい。

メモリー不足などもあり得るので、実際のコードではループを try で保護するべきだろう。

Find_Y_in() はバージョン1の Make_new_box() に当たる。

*1 の行はなくてもいいが、box[1]、box[2]…に含まれる要素数は計100万を超えることもあるので、用が済み次第、明示的に無効化しておく。

*2 は、検索結果を表示する。

グローバルなデータベース DB については、用が済んだら必ず無効化するべきだろう（*3）。参照可能のままだと、（ブラウザ上で実行しているとして）ページを開いている限り巨大オブジェクトが残ってしまう。

Get_upper_bound は、検索範囲の上界を返す。具体的には:

• 使う箱の最大個数 nBox が定義されているなら、「あ」によって、全数検索のための理論的な上界を返す。
• そうでなければ、「い」によって、簡易検索のための暫定的な上界を返す。

function Get_upper_bound( x, y, nBox, n ) // nBox: max number of boxes, n: current box number
{
    if( nBox ) return y * Math.pow( x, nBox - n ); // inaccurate if >= 2^53
    else return Math.pow( 2, n < 16 ? 24 : n == 16 ? 20 : 16 );
}

「上界の値自身は有効な範囲の一部（許容最大値）なのか、範囲外で無効なのか？」という境界問題は、常にバグの原因になる。ここでは「許容最大値」。値が2の53乗以上の場合、この計算には難点があるが、今回はその問題には立ち入らない。

MaxLimit を参照する Store は、呼び出しの最下層にある。どうやってそこまで情報を伝えるか。

• オブジェクト指向的に書くと、速度の低下傾向が見られた。
• 中間で使わないローカル変数を上から下まで次々と引数渡しするのも見通しが悪い。
• どこからでも書き換えられるグローバル変数だと、C でいう volatile の状態になって（変数を毎回読み直す必要が生じて）、遅くなるのではないか？

試してみたところ、この場合、変数を引数渡しにすると速度が少し低下し、グローバル変数の方がかえって速いようだ。ここではアルゴリズムを端的に紹介することを優先して、MaxLimit をグローバル変数とした。Y と DB についても同様。

入力値のエラーチェックは次の通り。|0 はダミーのビットOR。ビット演算を行うと暗黙に数値型・32ビット整数へのキャストが起きるため、入力がそれ以外（例えば非整数）なら、型または値が変わって弾かれる。

function Is_valid( x, y, nBox )
{
    if( nBox === void 0 || nBox === 0 ) nBox = DEF_NBOX;

    return ( (x|0) === x && x >= 1 && x <= MAX_X &&
            (y|0) === y && y >= 1 && y <= MAX_Y &&
            (nBox|0) === nBox && nBox >= 1 && nBox <= MAX_NBOX );
}

箱詰め管理・改良版（32行）

バージョン1の Make_new_box は、バージョン2では Y 発見時に true を返す仕様になり、Find_Y_in と改名された。

/// function Make_new_box( box, n ) // n: box number
function Find_Y_in( box, n, x )
{
    var new_box = box[n] = []; // Array!

    var found = false;

    if( n == 1 ) {
        found = Store( x, new_box );
    } else {
        for( var i = 1, last = (n >>> 1); i <= last && !found; ++i ) {
            if( i != n-i ) found = Mix( box[i], box[n-i], new_box );
            else found = Self_mix( box[i], new_box );
        }
    }

    return found;
}

new_box は、box[n] と同じ配列を指す。（理論上は、こんな名前を付けずに box[n] をそのまま他の関数に渡しても差し支えない。）

n>>>1 は、2³² 未満の負でない整数 n について、n/2 の整数部分を表す。この場合、last=n/2 と書いて 0.5 の端数を放置しても動作するし、事実上ほとんど違いはないだろう。しかし、余計な端数がない方がいいし、ビットシフトには速度的なメリットもある（付録参照）。

箱2以降の作成中、found は、ループ内において関数から戻り値を受け取る。その値は Y が見つかった場合にのみ true であり、そのときには !found が偽になってループが終わる。

以下の2個の関数は Find_Y_in から呼び出され、「ある箱と別の箱」または「同じ一つの箱」から順々に2個の数を選んで、Calc に渡す。

function Mix( boxA, boxB, new_box ) 
{
    for( var i = 0, lenA = boxA.length; i < lenA; ++i ) {
        for( var j = 0, lenB = boxB.length; j < lenB; ++j ) {
            if( Calc( boxA[ i ], boxB[ j ], new_box ) ) return true;
        }
    }
    return false;
}

function Self_mix( boxA, new_box )
{
    for( var i = 0, lenA = boxA.length; i < lenA; ++i ) {
        for( var j = 0; j <= i; ++j ) {
            if( Calc( boxA[ i ], boxA[ j ], new_box ) ) return true;
        }
    }
    return false;
}

箱詰め実務・改良版（20行）

Calc は通知された2数の間で四則演算を行い、生成された数を Store に送る。

function Calc( a, b, new_box )
{
    if( a < b ) { var tmp = a; a = b; b = tmp; } // [a,b]=[b,a] @ES6

    return ( Store( a + b, new_box )
            || a > b && Store( a - b, new_box )
            || Store( a * b, new_box )
            || a % b == 0 && Store( a / b, new_box ) );
}

バージョン2では箱の中身が数値なので、Calc 先頭での「文字列から数値への変換」は必要なくなった。a または b が 0 の場合、四則演算によって新しい数が生じないのは明らかだから、処理を省略できる。いっそのこと、引き算のとき a>b を要請して、最初から 0 を作らないようにしよう。そうすれば 0 は計算のどこにも含まれず（どの箱にも格納されず）、割り算の前のゼロ除算チェックも必要なくなる。

function Store( number, new_box )
{
    if( number > MaxLimit ) return false; // *1

    if( number > 9007199254740991 ) { // 2^53-1 // *2
        f53 = true; // global flag
        return false;
    }

    if( DB[ number ] ) return false; // *3

    new_box.push( number );
    DB[ number ] = true;

    return ( number == Y );
}

Store は、渡された数が上界を超えている場合（*1）、正確な処理が可能な最大値を超えている場合（*2）、データベースに登録済みの場合（*3）には、その数を受け付けない。それ以外の場合には、その数を new_box に追加し、データベースに登録する。

*2 の拒否は「MaxLimit 以下だが 2⁵³−1 を超える数」に対するもの。JavaScript において（一般に倍精度浮動小数点演算において）、2⁵³−1 を超える整数値は信頼できない（1以上の誤差を含む可能性が高い）。拒否すると全数検索にならないが、少なくとも「箱の中の数は全て正確」という保証が得られる。拒否しないと「信頼できない数」が箱に入り込み、それを経由した「間違った Y の作り方」が誤検出される可能性が生じる。従って、拒否する方が害が少ない。この状況が発生したら、目印として f53 フラグを立てておく。

ES6 では、2⁵³−1 に Number.MAX_SAFE_INTEGER という名前が与えられている。

バージョン1と違い、作成中の箱の中に同じ数があった場合、データベースで「既存」と判定されるため、再格納は行われない。そのため new_box は要素に重複のない配列となる。Y が生成された場合、Store が第一発見者となり、戻り値 true の連鎖をトリガーする。

関数を適当にネストすれば（さらには全体をクラス風にまとめれば）、new_box の受け渡しが不要になってコードが緊密になるが、それをやると速度が低下することがある。

検索結果の出力（13行）

function Show_results( x, y, answer, nBox )
{
    var message = ( "x=" + x ) + ( ", y=" + y ) + ( ", nBox=" + nBox ) + ": [ Results ] ";

    if( nBox ) {
        if( f53 ) message += "Maybe "; // f53: global flag
        if( answer ) message += ( "h = " + answer );
        else message += ( "h > " + nBox );
    } else {
        if( answer ) message += ( "h ≤ " + answer );
        else message += ( "Search failed!" );
    }

    alert( message );
}

• nBox が定義されていれば、これは全数検索の結果である。
  • answer は Y を含む箱の番号であり、「Y を作るのに使われた X の個数」を表す。この値がある場合、Y の作り方は判明しており、answer の値が求める解 h である。
  • answer が未定義の場合、全数検索の結果として「nBox 個以下の X では Y を作ることができない」と結論される。つまり h は、それより大きい。
  • ただし、いずれの場合も、f53 フラグが立っているときは真の全数検索ではなく、厳密性に傷がある。
• nBox が未定義なら、これは簡易検索の結果である。
  • answer がある場合、h は answer に等しいか、またはそれより小さい。（簡易検索なので、「上界を上げれば、もっと少ない個数の X で Y を作れる」という可能性が残る。）
  • 簡易検索なのに answer が得られなかった場合は、検索失敗。

nBox=0 は未定義と同じ扱いになる。（これをエラーにしたければ、Is_valid において nBox===0 を通さなければいい。）

結果が「検索失敗」になるケースでは、実際には多分、結果までたどり着けない: スクリプトの実行時間が長過ぎて強制的に中断されるか、メモリー確保に失敗して（捕捉可能な）例外が発生するだろう。

alert は純粋に説明のためのもので、現実のコードでは、もっとましな出力をページ上に書き出せばいい。

バージョン2の結果報告

「2015を作るには27が13個必要」という検証は、バージョン1では5.8秒もかかったが、バージョン2を使うと、0.1秒未満になった。実行時間は環境によって異なるが、相対的に速度が約170倍になった。

「2079を作るには91が16個必要」という証明は、高速化の途中では10秒以上かかっていたが、今では簡易検索0.3秒、全数検索0.6秒になった（f53 フラグが立ってしまうが、15個では作れないことは検証可能なので、解16は確定的）。

「2117を作るには129が17個必要」という解については、フラグが立ってしまうものの、簡易検索0.5秒、全数検索2.4秒だった。簡易検索のあと nBox=16 で全数検索すれば検証1.0秒であり、合計1.5秒で同じ結論が得られる（フラグは立ってしまう）。

「西暦・平成型」で2200年くらいまでを考えた場合、だいたい h=17 がワーストケースだ。それが実用的な時間で解けるようになった。

チューニングやアルゴリズムの改善により、さらなる高速化も可能だろう。例えば、DB として ECMAScript 2015 (ES6) で標準化された Map を使うと、上記の0.5秒/2.4秒が、0.4秒/1.8秒に短縮され、Set を使うと、0.4秒/1.6秒に短縮された（付録参照）。

[7/7] 結論と展望

一見「全数検索は不可能」とも思われる形のパズルだが、50～100行程度のシンプルなスクリプトによって、数秒で（多くは1秒以内に）全数検索が実行される。確かに計算量が壁になるが、地味な工夫を幾つか積み上げることで、結果的にブレークスルーが生じた。

まだ改善の余地・検討すべき課題も多い:

1. Y が作れた証拠として実際に X の式を出力しないと、パズルが解けた気がしない。その処理は簡単で、Calc と Store の処理を少し変えて、データベースには、各キーごとに「どういう二項演算でその数を作れたのか」というレシピを登録すればいい。そのデータベースを見れば、Y を発生させた二項演算が分かり、同じデータベースにより、その二項演算の2項のそれぞれのレシピも分かり、それらのレシピの材料のレシピも分かり…となって、芋づる式に X まで「分解」できる。
2. 「2通り以上の分解ができる場合に、どの分解をデータベースに書くのか」という点（レシピの優劣判定）は、また別の問題となる。
3. それらと合わせて、ブラウザ上から試せるデモを公開するべきだろう。
4. f53 フラグが立ってしまうケースにおいて、厳密性を保証するのは容易ではない。理想は、数学的考察により上界の評価を改善し、巨大な数を極力排除すること。次善の策は、64ビット整数をサポートしている言語を使い、扱える整数の上限を上げること。どうしても JavaScript でやるとなれば、53ビット以上の演算を自分で実装するか、その種のライブラリを使う必要がある。[追記: JavaScript の新しいバージョンでは、任意精度の整数演算がサポートされるようだ。]
5. 現在のアルゴリズムでは X から Y に向かって検索しているが、逆方向に検索するのはどうだろう？　つまり「X を2個使えば A と B と C が作れて、それらを組み合わせれば D と E と F が作れて…」とやる代わりに、「Y は S と T から作れるが、S は P と Q から作れて…」と帰納的に考えることもできる。状況によっては、その方が速いこともあるはずだ。
6. 整数以外の Y を効果的に検索できるか？　例えば:
   • 

以前にも似た問題を何度か紹介したことがあるが、そのときは「ラムダ関数」「文字列を作ってそれを動的に式として評価する方法」「関数を要素とする配列」といった技巧的な方法に走ってしまった。それはそれでワクワクするが、実はそんな面倒なことをしなくても、普通に+−×÷の計算をすればいい。本文の Calc がその実装例だ。技巧の探求も楽しいけれど、単純なやり方がかえって速ければ、実用上はそれが一番だろう。

付録

ECMAScript 2015 (ES6) の利用

ES6 の Map や Set がサポートされる環境では、次のようにすると速くなる。

• DB を new Map() として生成する。グローバル変数のままなら、使用後には DB.clear() で解放するべきだろう。
• 「データベースに数 c が既存か」を調べるには DB.has(c) を使う。データベースに c を追加するときは DB.set(c,value) を使う。value はそのキーに対応するレコードであり、何でも格納できるが、とりあえずダミーの 1 か true を書いておく。

本文の DB は Object なので、キーが（実質は数値だが）文字列となる。言うまでもなく、これは効率が悪い。整数 123 が文字列 "123" として格納されるからだ。Map では、数値が数値のままキーとなるので、効率が上がる。

それと比べると小さな問題だが、本文の例ではどのキーに対しても値が true なので、本来マップにする意味がない。本質的には「キーが定義されているかどうか」で既存・新規が判定され、キーが持つ値は利用されていない。従って、Map ではなく Set を使うと、ちょうどいい。その場合、値を追加するときは、DB.add(c) とする。データベースに「キーごとのレシピ・生成コスト」などの情報を格納する場合、Map が必要だが、値がダミーなら Set の方がすっきりする。

Set を「キーだけのマップ」であるかのように記述したが、実際には「値だけのマップ」。Set の中身を for ループで列挙したい場合、key in ではなく value of になる。

DB を配列にすると？

ES6 がサポートされていない環境においても、DB を数値の配列として、DB.push(c) で数値をそのまま格納することは可能だ。マップ風 Object よりメモリー的な効率は高いだろう。

ただしその場合、DB.has(c) に当たるうまいメソッドがない。

素朴に考えれば、DB.indexOf(c)!=-1 だが、これは「データベースに問い合わせるたびに、既存かどうか、端から1個ずつ要素を調べること」に当たり、速いわけがない。ES7 には DB.includes(c) もあるが、仕様書を見る限り速くない。やるなら、配列をソートしてバイナリーサーチだろう。といっても、検索・挿入のたびに sort() を呼んでソートし直すわけにはいかない。配列を常にソート済みに保っておいて、「渡された数 c が既存だとすれば、配列のどこにあるか」をバイナリーサーチで調べ、その位置に実際その数があれば「既存である」と却下し、その数がなければ「新規なので受け付けます」と、その位置に挿入すればいい。この方式を仮に「自己ソート配列」と呼んでおく。

問題は「新規なので受け付けます」というとき、ソートされた位置（配列のど真ん中）にどうやって要素を挿入するのか、という点だ。コード上では splice() により簡単にできるが、内部的には運が良くても大規模な memmove、運が悪ければ配列全体の再確保が起きると予想される。要素数が1万や10万単位、場合によっては100万単位になる配列では、とてもスケールしないだろう。

本文と同じアルゴリズムで Search(27,2015); とすると、データベースの項目が約8万件になる（件数自体は MaxLimit のチューンで減らせるが、そこは本題ではない）。この例について、DB.indexOf(c)==-1 ならプッシュ…とした場合、テスト環境において全体の実行時間が5秒以上だった。「自己ソート配列」を使うと、実行時間が1.1秒になった。さらに、splice の呼び出しを避けると、0.8秒台にできた。しかし素直に Object のプロパティーをマップ風に使った場合（本文と同じ方法）、同じことが0.1秒未満でできる。

5通りのやり方と、所要時間の例:

DB=[]; if(DB.indexOf(c)==-1) DB.push(c); // too slow (5200 ms)

DB=[]; DB_accept(c); // better but slow (1100 ms/880 ms)

DB={}; if(!DB[c]) DB[c]=true; // much faster (70 ms)

DB=new Map(); if(!DB.has(c)) DB.set(c,1); // ES6 (50 ms)

DB=new Set(); if(!DB.has(c)) DB.add(c); // ES6 (50 ms)

「自己ソート配列」DB_accept(c) の実装は次の通り。

自己ソート配列（17行）

「渡された数が配列内に既存なら何もせず false を返す。新規の数なら配列内のソートされた位置にそれを挿入し true を返す」。例えば:

var DB = [];
DB_accept(5);  // true   DB=[5]
DB_accept(3);  // true   DB=[3,5]
DB_accept(8);  // true   DB=[3,5,8]
DB_accept(11); // true   DB=[3,5,8,11]
DB_accept(8);  // false  DB=[3,5,8,11]
DB_accept(12); // true   DB=[3,5,8,11,12]
DB_accept(6);  // true   DB=[3,5,6,8,11,12]
DB_accept(10); // true   DB=[3,5,6,8,10,11,12]
DB_accept(5);  // false  DB=[3,5,6,8,10,11,12]
DB_accept(2);  // true   DB=[2,3,5,6,8,10,11,12]

前提として、DB を最初に空の配列として生成し、配列の書き換え（要素の追加）を全てこの関数経由で行う必要がある。同じ要素を複数回追加しても、最初の1個しか追加されない点は、Set 風。

function DB_accept( number ) // works ok if DB.length is small
{
    var len = DB.length, start = 0, end = len, index = 0; // DB: array

    while( start < end )
    {
        index = (( start + end ) >>> 1 ); // *0
        var value = DB[ index ];

        if( value < number ) start = index + 1;
        else if( value > number ) end = index;
        else return false;
    }

    if( index < len && DB[ index ] < number ) ++index; // *1
///    if( DB[ index ] < number ) ++index; // *2

///    DB.splice( index, 0, number ); // *3
    DB.push(0); // *4
    for( var i = len; index < i; --i ) DB[i] = DB[i-1]; // *5
    DB[ index ] = number; // *6

    return true;
}

*1 の代わりに *2 と書いても動作するが、その場合、配列の末尾要素の後ろの要素を読んでしまうことがある。結果は undefined（未定義値）だが、仕様書によると undefined は数値としては NaN に変換され、NaN との大小比較の結果は再び undefined。これはブール値としては false なので、インクリメントは起こらない。結局意図通りだが、危なっかしい。

配列に物を挿入する処理は、*4～6 のようなことをしなくても、splice の1行で済む（*3）。普通はそうする。しかし *5 のように自分で1個ずつずらして、空いた隙間に *6 の書き込みを行う方が高速になることがある。Firefox 上のテスト例で、1100 ms⇒880 ms となった。これ自体は（ソートと関係なく）どんな配列にも使える方法だ。ただし、*4 のように先にダミーのプッシュをしないと、逆にひどく遅くなった。ループに入ったとたんメモリーの再確保が起きると、ポインタが全力疾走できずリズムが乱れるのだろう。実はダミーのプッシュを *1 の前で行い、DB.push(number) としておくと、*1 の条件を削った *2 の書き方が安全になる。

しかし、このように頑張っても、伝統的な「オブジェクトのマップ風」より速くならない。配列の長さが10万単位のとき、「マップ風」に勝つには、あと10倍以上速くする必要がある。スケールが拡大すると、ますます負けるだろう。1個レコードを追加するごとに数万件のデータが移動するのは、まずい！

「再割り当てが起きないように最初から巨大サイズの配列を確保して、自分で長さを管理」というのも数パターン試したが、速くならなかった。（ES6 なら面白いこともできそうだが、ES6 でいいなら本物のマップが使える。）

結局「自己ソート配列」が実用になるのは、配列の長さが比較的小さい場合に限られる。常にソート済みなので、使いどころによっては便利だろう。「挿入頻度は低いが、要素の有無を問い合わせる回数が非常に多い」という状況では、意外といいのかもしれない（問い合わせ用のメソッドを別に用意するとして）。

*0 の行の丸括弧は、論理的には全く必要ない。意図を明確にし、優先順位の錯覚による間違いを予防するために付けてある。

整数を2・4・8・16…倍するときや整数を2・4・8・16…で割って余りを捨てるときのビットシフトは、C/C++ では使い古された方法だが、JavaScript の世界では、必ずしも普及していないようだ。sorted-array（参考になる！）では、2で割ってから >>>0 している。Stack Overflow では、2で割ってから parseInt を呼んでいる。Searching JavaScript arrays では「2で割ってから Math.floor」という実装を改訂して、2で割ってから |0 している。

当たり前のことだが、2で割ってからダミーのビット演算で整数型にキャストするくらいなら、割り算せずに右に1ビットずらすべきだ。実際、「2で割ってからビット演算」だと、この例では 880 ms⇒910 ms という速度低下が起きた。CPUが進化した現代でも、相変わらず割り算は遅い。

補足

JavaScript の右シフト演算子のうち、

1. >>> は「内部的に32ビット符号無し整数にキャストした後で、論理シフト」
2. >> は「内部的に32ビット符号付き整数にキャストした後で、算術シフト」

を行う。これらは「割り算のための演算子」ではないが、以下の用法において、浮動小数点数の割り算より処理が速い:

1. a が 0 以上 2³² 未満の整数で、b が 0 以上 31 以下の整数の場合、a>>>b によって「a を 2^b で割って商を floor 処理する」のと同じ結果が得られる。
2. a が −2³¹ 以上 +2³¹ 未満の整数の場合、a>>b によって同様の「割り算」が実行される。「商」は、正負にかかわらず floor 処理される。

シフト実行前のキャストにおいては、正負にかかわらず、端数は切り捨てられる（正の数は floor 処理され、負の数は ceil 処理される）。

付録のまとめ

• マップ風 Object は（キーが文字列というハンディがあっても）かなり速い。ただし、ES6 の Map の方がもっと速い。
• splice を自分で書くと、速くなることがある。
• 整数 a について a/2 の端数を切り捨てたいとき、割り算をやめて a>>>1 と書くと動作が速い。ただし、有効範囲と符号の問題に注意。

「西暦・平成パズル」を解くアルゴリズム > 更新履歴

1. 2016年3月27日: 初版公開。
2. 2016年4月1日:
   • 付録の内容の修正・改善。(1) まとめの部分で「a が整数」という条件が抜けていた。 (2) 「マップを検索する回数」⇒正しくは「要素の有無を問い合わせる回数」。 (3) 右シフト演算子について補足。
   • 実行時間の計測を一部やり直した（初版との差は小さく、実質的な違いはない）。
   • 表現の細部の調整（約30カ所）。一部の数式を画像化。飾りの画像（全てパブリックドメイン）を追加。
3. 2016年4月3日:
   • 「箱詰め実務」の説明を改善。「有効範囲内だが拒否」という処理の意味を明確にした。
   • 表現の細部の調整（約10カ所）。誤字修正（1カ所）。
4. 2016年4月10日: 表現の微調整（3カ所）。
5. 2019年3月10日: 表記修正: 「保障」→「保証」
6. 2019年11月29日: 誤字修正: 「並び替え」→「並べ替え」
7. 2023年4月1日: JavaScript自身による任意精度演算サポートについて追記。