２．ループの高速化

a についてのしらみつぶし探査は o(n) のオーダーなので、
桁数を 1 桁上げるために10倍の計算時間が必要になる。
何か工夫が欲しい。

b = a² の下 n 桁の数字は、a の下 n 桁の数字のみによって決定される。
例えばある数 a について b = a ²を計算するとき、
b の下 5 桁で 4 種類以上の数字が出現すれば、それ以上、上の桁まで計算する意味はない。
そこで、例えば 1 ≤ g ≤ 99999 の g に対して、 g² の下 5 桁の数字が 3 種類以下となる数だけを、配列 w(i) に格納しておき、

a = 100000 * h + w(i), h は任意

についてのみ調べる、という方法が考えられる。これで、かなりループの回数が減るはずである。

尚、初めの下 5 桁の数字のチェックで、前述のアルゴリズムを適用するには、多少工夫が必要である。
例えば a = 13 の時 a²=169=00169 なので下 5 桁は 4 種類の数字から成るが、len(169) = 3 だからループは３回で終わってしまい、３種類の数字から成る、と判定されてしまう。
00169 という形で判定したい。

これの回避方法は簡単で、例えば、探査範囲を100001 ≤ g ≤ 199999とし、下 5 桁のみに着目すればよい。

w(i) を格納する配列の要素数は減らすことができる。

(100000+g)² = 10¹⁰ + 200000 g + g²
(100000-g)² = 10¹⁰ - 200000 g + g²

であるから、100000+g と100000-g を 2 乗した場合、下 5 桁は一致する。
従って、g の範囲は、100001 ≤ g ≤ 149999 としてよい。
さらに、

(50000-g)² = 25 * 10⁸ - 100000 g + g²

であるから、g と 50000-g を 2 乗した場合、下 5 桁は一致する。
従って、g の範囲は、100001 ≤ g ≤ 124999 としてよい。
これで、配列の要素数は 1/4 で済む。
さらに、この範囲の数であれば、配列として整数型で桁数が足りる。

以上で、かなり高速化が期待できる。

アルゴリズムは以下のとおり。

    for g = 100001 to 124999
      下 5 桁の数字の判定。
      1. のアルゴリズムで、下位の桁から 5 桁分のみをチェックする
      3 文字以下なら、g@100000 を配列 w(i) に格納する
    next g

    h = 0
*   for i = 1 to m : a = 100000h + w(i) : gosub ** : next i
    for i = m to 1 step - 1 : a = 100000h + 50000 - w(i) : gosub ** : next i
    for i = 1 to m : a = 100000h + 50000 + w(i) : gosub ** : next i
    for i = m to 1 step - 1 : a = 100000h + 100000 - w(i) : gosub ** : next i
    inc h : goto *

**  ' サブルーチン
    a2 について、何種類の数字から構成されているかを調べる
    3 種類以下なら、a, b = a2 を表示する
    return

このアルゴリズムで求めた、a ≤ 10⁹ 以下の個別解は次頁のとおり。
（パターン解については、後でまとめて示す）