5.追補

読者からのメール (1997/06/15)

Subject: 回文数について
Date: Sun, 15 Jun 1997 04:58:10 -0700
From: Koji Yamashita

三島久典様。

はじめまして。
回文数に関するH.P読ましていただきました。
私も、回文数の計算をPC9821Xa(Pentium90MHz,メインRAM24MB)で、UBASICで2
桁から7桁までの数すべて計算しました。ただ、私のパソコンとプログラムで
は、ここらが限界かなと思って一休みです。8桁の数すべての計算については、
あまりに時間がかかりすぎるので、(私のパソコンとプログラムでは、2400時間
位?)、パソコンを買い換えてからの、宿題にしようと思っております。
私の計算では、7桁までの数で時間のかかる回文数は、9928009で、96回で48桁の
回文数になります。
196についても、22000回、9136桁までは計算しました。なぜか、私のUBASICのプ
ログラムではここでとまってしまいました。
三島さんのプログラム(UBASIC? OR C?)とパソコン(?)では、8桁の数すべての
回文数の計算時間はいかほどの見込みでしようか。では

          住吉学園高等学校 数学科 山下幸二

高速化のための手段

処理を速くする、或いは、探査範囲を拡げる(試行回数を増やす)には、
一般に以下の手順が考えられる。

  1. ループの回数を減らす(試行対象を減らす)
  2. ループの中の処理を簡略化する
  3. ぜんぜん別のアプローチを考える

最初に述べたとおり、例えば196を調べたのなら、295, 394, 493, 592, 691 を調べる必要はない。
明らかに、次の足し算のフェーズで同一になるからである。
このことを一般化する。

7桁の数、

a1 a2 a3 a4 a5 a6 a7

を例として考える。

7桁の数は、1000000〜9999999 の 9000000個だが、上の要領で、調べる必要のないものがいくつかある。

まず、

a1 ≤ a7
a2 ≤ a6
a3 ≤ a5

の場合のみ調べればよいことは容易にわかる。

このそれぞれの取りうる値は、

(a1,a7)

(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(1,8),(1,9)
(2,9),(3,9),(4,9),(5,9),(6,9),(7,9),(8,9),(9,9) 計17個

(a2,a6),(a3,a5)

(0,0),(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(0,7),(0,8),(0,9)
(1,9),(2,9),(3,9),(4,9),(5,9),(6,9),(7,9),(8,9),(9,9) 計19個

a4(桁数が奇数の場合のみ)

0, 1, 2, 3, 4, 5, 6, 7, 8, 9 計10個

よって、7桁の数で調べるべき数の総数は、

17 * 19 * 19 * 10 = 61370

これは、最初の 9000000 に比べると、劇的に減っている。
さらに、それ自身回文的になっている数は調べる必要がないので、さらに数が減る。

各桁の数で、調べるべき数の個数は、以下のとおり。

桁数範囲総数見積もり回文数を除去
210〜99901715
3100〜99990017 * 10 = 170150
41000〜9999900017 * 19 = 323319
510000〜999999000017 * 19 * 10 = 3230
6100000〜99999990000017 * 19 * 19 = 6137
71000000〜9999999900000017 * 19 * 19 * 10 = 61370
810000000〜999999999000000017 * 19 * 19 * 19 = 116603
9100000000〜99999999990000000017 * 19 * 19 * 19 * 10 = 1166030
101000000000〜9999999999900000000017 * 19 * 19 * 19 * 19 = 2215457
1110000000000〜999999999999000000000017 * 19 * 19 * 19 * 19 * 10 = 22154570
12100000000000〜99999999999990000000000017 * 19 * 19 * 19 * 19 * 19 = 42093683
131000000000000〜9999999999999900000000000017 * 19 * 19 * 19 * 19 * 19 * 10 = 420936830
1410000000000000〜999999999999999000000000000017 * 19 * 19 * 19 * 19 * 19 * 19 = 799779977
15100000000000000〜99999999999999990000000000000017 * 19 * 19 * 19 * 19 * 19 * 19 * 10 = 7997799770

上述の山下氏の得た解 9928009 は、ここで述べた方法と、不等号の向きを逆で計算した結果となる。 それにしても、7桁の場合の調べるべき総数 61370 に対し、8桁の場合の 116603 は、7桁の場合の1.9倍だから、充分射程に入っている。 少なくとも、2400時間という見積もり程は、かからない。

私の 486DX2, 66MHz のパソコンでも、12〜13桁ぐらいなら、充分行けるだろう。
Pentium 90MHz なら、もう2桁上ぐらいは行けるか。
(という訳で、現在のPCなら、かなり先まで行けるはずである。再計算してみる価値あり)

ちなみに、この調べるべき数というのは、まず初めに1度だけ計算して、ファイルに吐き出しておく。
足し算、回文性チェックのフェーズにおいては、このファイルから読み出して処理を行うようにする。


今は、調べるべき総数を減らした。次にループの中の処理を短くすることを考える。
といっても、足し算、及び、回文性チェックルーチンは、これ以上劇的に短縮することはできない。

前はループ回数(足し算、回文性チェック)を一律200回とした。
しかし、大半の数は、より少ない回数で収束するか、収束しないかのどちらかである。
よって、

とする。収束しない数については、何回も同じことを繰り返すことになるが、
そもそも収束するかしないかはわからないので、このようにふるい落としていくのが本筋である。
また各フェーズの時間が短くなるので、中断・再開始ができる(つまり、途中でPCで電源を落とせる)。

また、大半の数は、重複チェックで落とせるはずである。よって、

とする。この過程において、先ほどのマスタファイル(調べるべき数)から、どんどんふるい落としていく。
これで、全体の試行回数がかなり減るはずである。

さらに、途中経過を利用する方法が考えられる。
そもそも調べなければならないのは、素性のわからない数のみである。
すなわち、素性のわかっている数(収束する、或いは収束しそうにない)は、 あらためて調べる必要はない。

例えば、2桁の数は必ず収束する。
この2桁の数が収束するまでの途中経過を保存しておき、
3桁の数の探査を行うときには、この前段階で生成された素性がわかっている数
(2桁の数の収束するまでの途中過程(3桁になったときの状態))
は、探査対象から外すことにする。
この処理は、マッチング処理の典型的なパターンであり、
ファイルサイズ(探査対象の数の個数)をnとしたとき、2nのオーダの処理である。
従って、計算時間の延びは、あまり気にする必要がない。

これにより、探査対象は、さらに劇的に減るはずである。

以上の対策を一通り全て行うなら、あと1〜2桁は探査範囲が拡がると思う。
私の 486DX2, 66MHz パソコンで、14〜15桁ぐらい、
Pentium 90MHz なら、16〜17桁ぐらい、
というところか。いずれにせよ、8桁は完全に射程の範囲内である。
(現在のPCなら、もっと、かなり先まで行けるはず)

196に挑戦するには、まず、配列の確保のしかたを考える必要がある。
Windows me 以前であれば、DOSプロンプトでEMSが使えたので、 UBASICでEMS上に配列が確保できたが、 現在の Windows では EMS が使用できない。 よって、配列サイズを増やそうと思ったら、Linux 或いは、Windows 上で Cygwin を使うしかない。

……とりあえず思いつくのは、こんなところである。
コーディング例を示さなかったが、云わんとしているところは、わかると思う。
どなたか、挑戦してみませんか?


(1999/06/28) Cygnusという、GNUコードのWin ネイティヴ版 gcc の存在を偶然知り、 久しぶりに計算をやってみた。
9928009(96回)の次の数として、

100239862(97回)

が見つかった(8桁では無し)。
これ以降については、もともとのページの方を更新した。


この章の目次

E-mail : kc2h-msm@asahi-net.or.jp
三島 久典