すたっきゅん数を効率良く見つける方法

Algorithm

1. 概要

すたっきゅん数とは、
【定義】10^N 未満の自然数 n であって、 n^2 を10進法表記して同じ数が連続で N+1 個以上並ぶ数のうち、 n≡0 (mod 10) でないものを「すたっきゅん数」と定義する
こんな数です。

2. 普通に見つける方法

nを小さい方から試していって、上の定義に沿っているものを集めれば、すたっきゅん数が発見できます。
しかし、この方法では桁数が大きくなるとすぐに発見できなくなってしまいます。10桁程度でも、数十分から数時間程度かかってしまうようです。

3. 効率のいい方法

n^2=mとします。mについて全探査をかけることを考えます。
定義より、mは同じ数を連続してN+1個以上含みます。まず、ここで現れる数と、その位置について全探査をかけます。
今、N=6で、m=****2222222* と表されるとします。（*は任意の桁）
ここで、*を全探査してそれぞれに対してnを求めていたのでは、全く改善されてないので、全探査の範囲を絞ります。
mにおいて、*の連続部分が2つあります。そこで、どちらの連続部分が大きいかで処理を変えます。

i. 前の部分のほうが大きい場合

後ろの部分のほうが小さいので、後ろの部分に対して全探査をかけます。
今、m=****22222225 となったとします。
そして、前の部分を決定することを考えます。これは、nの下のほうの桁から順次決定することで、比較的高速に（少なくとも全探査よりは圧倒的に速いです）前の部分を決定もしくは、該当するnがないと決めることができます。

ii. 後ろの部分のほうが大きい場合

前の部分のほうが小さいので、前の部分に対して全探査をかけます。
例えば、m=433333333**** とします。
すると、m=n^2であり、4333333330000<=m<4333333340000 であるので、
2081665.999 <= n < 2081666.001 が成り立ちます。よって、n=2081665とわかります。もちろん、当てはまるnがない場合もあります（それがほとんどです）。この処理も、普通に後ろの部分を全探査するよりずっと速いです。

この2つのどちらかの処理によって、N桁のすたっきゅん数のリストを作成することができます（この処理では、実質mに対して全探査をかけているので、nに対して全探査をかけているも同然で、すべてのすたっきゅん数を網羅できます）。これはソートされていなかったり、同じものを2回数えていたりするので、そういうのを直して出力すればいいです。

この方法をうまく実装すれば、10桁のすたっきゅん数列挙も20秒程度で完了します。