n=89のとき24回の足し算の末に回文的になったまではよかったが、n=196 で終了してしまった。
回文的にならなくて配列の範囲を越えたらしい。
n=295 、394 も同じであることは目に見えている(∵ 196+691=295+592=394+493)。
ならば MAXの値を100から一気に 10000ぐらいにして試してみよう、と考えるのは自然な発想である。
が、先に結論を云ってしまうと、10000 でもやはり終了してしまう(回文的にならない)。
実はこれは有名な未解決問題であり、196 が回文的になるかどうかは現在のところわかっていない。
そこで方針を変えて、以下の3つの場合に分けて検討を行うことにする。
1.はプログラムの改造は必要ないが、今回はやらない。
未解決といっても、どの程度未解決かはよくわからないので、MAX=100000程度で収束する可能性もある。
やりたい人は一度試してみる価値はある。
ここでは2.と3.を扱ってみる。
しらみつぶし探査をする時、例えば 196 と 691 は同じ結果になるので、どちらかは調べる必要がない。
逆順に見たときに対応する上位と下位の数字を比較して、上位≦下位、となる数のみを調べることにする。
そのための判定ルーチン(n_check())を下に示す(UBASIC ではなく、C のコード)。
flag=0; for(i=1, j=n; i<j; i++, j--) if(a[j]>a[i]){ flag=1; break; } return flag;
(2) を実現するためには MAXを極端に大きくする必要はない。とりあえず、200 ぐらいにしておく。
足し算の結果あふれるようなものは、196 のような部類の数であるとみなし、
本当に収束しないのか、かなり時間がかかった末に収束するのか、あらためて、個別に調べていく。
nの最大値を格納するための変数を用意して(例えば、maxvとする)初期値は1にしておき、
収束するたびに countとの比較を行う。
count > maxv なら countの値を printし、maxv=countとする。小さい時は何もしない。
計算結果は以下のとおり。
palindromic | count |
---|---|
59 | 3 |
69 | 4 |
79 | 6 |
89 | 24 |
10548 | 30 |
10677 | 53 |
10833 | 54 |
10911 | 55 |
147996 | 58 |
150296 | 64 |
1000689 | 78 |
1005744 | 79 |
1007601 | 80 |
7008899 | 82 |
9008299 | 96 |
100239862 | 97 |
140669390 | 98 |
1005499526 | 109 |
10000442119 | 112 |
10000761554 | 113 |
10000853648 | 131 |
10000973037 | 135 |
10031199494 | 147 |
10087799570 | 149 |
1000006412206 | 186 |
Helmut Postlは、さらに大きい例10000000525586206 (232 times)を見つけた。(June 22, 2001)
まず、発散する数を格納するための配列を用意する(inf[ ] とする)。
まず始めに見つかったものは無条件で格納するが、それ以降に見つかったものは、
前に見つかったものとの比較を行う。
やり方としては、前に見つかったものを発散するまで足し算して、
その中間結果との比較を順次行っていく。そのためのワークを用意する(t[ ][ ] とする)。
実行結果として各系譜の最小の数を順次表示していくと、
100万以下については次のとおり。
もちろん、これらが本当に別の系譜かどうか、本当に収束しないかどうかは、
さらに先まで計算してみないとわからない。
前 | この章の目次 | 次 |
---|