196 問題を解くための大きな整数の取り扱い

ライブスクリプトを開く

この例では、Symbolic Math Toolbox™ を使った、大きな整数とその 10 進数表現の処理方法を説明します。

回文

ある文字列が後ろから読んでも同じ文字列の場合、それを回文と呼びます。正の整数でその 10 進数表現が回文の場合、それは回文と呼ばれます。たとえば、191、313 および 5885 はすべて回文です。

以下のアルゴリズムを考えます。

任意の正の整数 $N$ を考え、それにその鏡像を加算します。
回文を得られるまで、結果の数値にこの手順を繰り返します。

たとえば、N=89 とすると、最初の 3 回の反復で以下が得られます。

$89 + 98 = 187$

$187 + 781 = 968$

$968 + 869 = 1837$

最終的に、24 回の反復後、回文 8813200023188 に達します。

N = sym(89);
for k=0:100
    s1 = char(N);
    s2 = fliplr(s1);
    if strcmp(s1, s2)
       disp(['Finished in iteration ' num2str(k)]) 
       break
    end    
    N = N + sym(s2);
    disp(N)
end

 $187$

 $968$

 $1837$

 $9218$

 $17347$

 $91718$

 $173437$

 $907808$

 $1716517$

 $8872688$

 $17735476$

 $85189247$

 $159487405$

 $664272356$

 $1317544822$

 $3602001953$

 $7193004016$

 $13297007933$

 $47267087164$

 $93445163438$

 $176881317877$

 $955594506548$

 $1801200002107$

 $8813200023188$

Finished in iteration 24

196 問題

このアルゴリズムはすべての $N$ で終了するでしょうか。

この問題はまだ解決されておらず、この問題の名前となった $N = 196$ のケースに対し、回文愛好家は多くの CPU 年を注ぎ込んできました。MATLAB® でこの問題に取り組むには、そのサイズに制限がないことから、シンボリック整数を使うと便利です。関数 sym を使用して 10 進数の文字列をシンボリック整数に変換し、char (num2str ではありません) で変換を戻します。

有名な $N = 196$ のケースが本当に大きな数値になることを調べます。整数の 10 進桁数の確認には、単純に log10 を使用します。

N = sym(196);
for k=0:1000
    s1 = char(N);
    s2 = fliplr(s1);
    N = N + sym(s2);
end
disp(['Number of digits after ' num2str(k) ' iterations: ' char(ceil(log10(N)))]);

Number of digits after 1000 iterations: 411