Twitterで見掛けた面白問題に挑戦してみた。
- 任意の自然数を用意する(例：777)
- 各桁の数字を全て掛け合わせる操作を1回とする(例：777 → 7×7×7 → 343)
- 掛け合わせた結果に対して同じ操作を繰り返す(例：343 → 3×4×3 → 36)
- 結果が1桁になったら終了(例：777 → 343 → 36 → 18 → 8)
- 操作回数がより大きい自然数を求める(例：777 → 4回)
なんでも12歳の子が、pythonを用いて授業時間内で11回の解を叩き出したそうで、大人として負ける訳にはいかない。
大まかな方針を決める
「任意の自然数」と聞いて1から順に試行するのがまず一案だが、即却下。
例えば「12, 112, 1112, ...」と考えてみれば、いくらでも大きな数になり得るのにどれも同じ結果になるのは明白。
これらを全て検証するのは無駄無駄無駄ァァァ。
では1回以上の操作を経た数についてはどうだろうか。
因数となり得るのは0~9の1桁の数が10種類。2桁以上の素数が入り込む余地は無い。
4, 6, 8, 9 は更に素因数分解できるので、これらも考慮する必要が無い。
0 は即BANだし、1 は有っても無くても関係無いから、残るのは 1桁素数の 2, 3, 5, 7。
これらのみを素因数として構成可能な数字を対象とすれば、それだけでもかなり検証範囲を絞り込めそうだ。組み合わせが異なれば重複することもない。
そんな訳で、方針は以下。
- 最初の自然数ではなく、1回目の操作が済んだ状態の数を探索する
- 探索範囲は 1桁素数(2, 3, 5, 7)のみを素因数とする数に絞り、異なる組み合わせのパターンを検証する
プログラム書いて検証
自分の場合、この手の問題では Perl を採用することが多い。今は亡き CodeIQ でも Perl のみで解答してきた。落ち目だと言われ続けて幾星霜。一向に消える気配がないのは謎だが、やはり手に馴染んだ道具を使うのが一番良い。
そんな訳で、職場で昼休みを利用して30分ほどで書いたコードが以下。
※コメントは書き足した。全く効いてなかった余計なコードは恥ずかしいので消した。(ぉ
#!/usr/bin/perl
# 桁あふれを防ぐために用いる基数2での指数値
my $log2_3 = log(3) / log(2);
my $log2_5 = log(5) / log(2);
my $log2_7 = log(7) / log(2);
# 探索の対象となる 1桁素数のみを素因数とする数を収集
my @values;
my $v2 = 1;
# 素因数2を符号無し64ビット整数の範囲内でループ
for (my $n2 = 0; $n2 <= 63; ++$n2, $v2 *= 2) {
my $max3 = int((64 - $n2) / $log2_3);
my $v3 = 1;
# 素因数3を符号無し64ビット整数の範囲内でループ
for (my $n3 = 0; $n3 <= $max3; ++$n3, $v3 *= 3) {
my $max5 = int((64 - $n2 - $log2_3 * $n3) / $log2_5);
my $v5 = 1;
# 素因数5を符号無し64ビット整数の範囲内でループ
for (my $n5 = 0; $n5 <= $max5; ++$n5, $v5 *= 5) {
my $max7 = int((64 - $n2 - $log2_3 * $n3 - $log2_5 * $n5) / $log2_7);
my $v7 = 1;
# 素因数7を符号無し64ビット整数の範囲内でループ
for (my $n7 = 0; $n7 <= $max7; ++$n7, $v7 *= 7) {
my $val = $v2 * $v3 * $v5 * $v7;
# いずれかの桁に 0 を含む場合は即BANするので対象外
if ($val !~ /0/) {
push @values, $val;
}
}
}
}
}
# 絞り込んだ結果の件数
my $length = @values;
print "$length\n";
my $max = 0; # 最大回数(初手の1回は含まない)
my @max_vals; # 最大回数を記録した解
foreach my $val (@values) {
my $cnt = 0;
my $v = $val;
# 1桁になるまでループ
while ($v > 9) {
# 全桁の数字を掛け合わせる操作
$v = multiply($v);
# 操作回数加算
++$cnt;
}
# 最大値更新なら回数と解を更新
if ($cnt > $max) {
$max = $cnt;
@max_vals = ($val);
# 最大値タイ記録なら解追加のみ
} elsif ($cnt == $max) {
push @max_vals, $val
}
}
# 結果発表
print "max: $max\n";
foreach my $max_val (@max_vals) {
print "max_val: $max_val\n";
}
exit;
# 与えられた数を桁毎に分解し、全て掛け合わせた数を返すサブルーチン
sub multiply {
my $val = shift;
my @digs = split(//, $val);
my $ans = 1;
foreach my $dig (@digs) {
$ans *= $dig;
}
return $ans;
}
ideone上で実行してみると、11回に相当する2つの解を0.1秒未満で得ることができた。
12歳のpython使いより全然速いぞ。エッヘン。
なお、1つ目の解 937638166841712 は 2^4 × 3^20 × 7^5 。2つ目の解 4996238671872 は 2^19 × 3^4 × 7^6 である。
1回目の操作でこれらの数へと変換できる自然数は無数にあり、例えば前者であれば 27777789999999999、後者であれば 277777788888899 がそれぞれ最小値となる。
ちなみに、どちらの数も 2回目の操作で 438939648 即ち 2^12 × 3^7 × 7^2 となり、その後は全く同じ過程で 1桁になるまでに計11回の操作を要する。
11回を超える解は見つかるのか？
上のコードでは対象を符号無し64ビット整数の範囲に限定していたが、その制限を取っ払えばもしかしたら12回以上の解も見つかるかも知れない。
という訳で、Math::BigInt を用いた検証を行なうことにする。
コードも少し改良してみた。
#!/usr/bin/perl
use Math::BigInt;
my $t = time();
# 桁あふれを防ぐために用いる基数2での指数値
my $log2_3 = log(3) / log(2);
my $log2_7 = log(7) / log(2);
# 演算に用いるため、1桁整数を Math::BigInt 型で予め用意
my @big = map { Math::BigInt->new("$_") } (0 .. 9);
# 最大符号無し整数のビット長
my $col = 2048.0;
# 探索の対象となる 1桁素数のみを素因数とする数を収集
my @values;
# 素因数2を符号無し最大ビット長整数の範囲内でループ
my $v2 = $big[1];
for (my $r2 = $col; $r2 > 0.0; $r2 -= 1.0, $v2 *= $big[2]) {
printf("r2:%d (%d) %d\n", $r2, time(), $#values + 1);
# 素因数3を符号無し最大ビット長整数の範囲内でループ
my $v23 = $v2;
for (my $r3 = $r2; $r3 > 0.0; $r3 -= $log2_3, $v23 *= $big[3]) {
# 素因数7を符号無し最大ビット長整数の範囲内でループ
my $v237 = $v23;
for (my $r7 = $r3; $r7 > 0.0; $r7 -= $log2_7, $v237 *= $big[7]) {
# いずれかの桁に 0 または 5 を含む場合は即BANするので対象外
if ($v237 !~ /[05]/) {
push @values, $v237;
}
}
}
}
# 絞り込んだ結果の件数
my $length = @values;
print "$length\n";
my $max = 0; # 最大回数(初手の1回は含まない)
my @max_vals; # 最大回数を記録した解
foreach my $val (@values) {
my $cnt = 0;
my $v = $val;
# 1桁になるまでループ
while ($v > 9) {
# 全桁の数字を掛け合わせる操作
$v = multiply($v);
# 操作回数加算
++$cnt;
}
# 最大値更新なら回数と解を更新
if ($cnt > $max) {
$max = $cnt;
@max_vals = ($val);
# 最大値タイ記録なら解追加のみ
} elsif ($cnt == $max) {
push @max_vals, $val
}
}
# 結果発表
print "max: $max\n";
foreach my $max_val (@max_vals) {
print "max_val: $max_val\n";
}
exit;
# 与えられた BigInt を桁毎に分解し、全て掛け合わせて BigInt で返すサブルーチン
sub multiply {
my $val = shift;
my @digs = split(//, $val);
my $ans = $big[1];
foreach my $dig (@digs) {
$ans *= $big[$dig];
}
return $ans;
}
処理速度を上げるためにちょいちょい細工はしたが、基本的な動きは64ビット制限版と何も変わらない。
2048ビット(10進で600桁超)まで探索範囲を拡大したものの、対象となった数は最大でも 4613824623662469877463718941499166849983276122112(= 2^132 × 3^1 × 7^10)に過ぎす、10進で 49桁、2進でもわずか 162ビットに収まってしまう。
おそらく11回を超える解は、これ以上探索範囲を広げても見つからないだろう。
【2019-08-26 追記】
Wikipediaによれば、11回を超える解は存在しないと考えられているし、10^20000まで探索して未だ見つかっていないらしい。
For a radix of 10, there is thought to be no number with a multiplicative persistence > 11:
this is known to be true for numbers up to 10^20000.
10^20000より大きい数の中から、(2, 3, 7)のみを素因数として各桁すべての積が少なくとも前述の49桁以内に収まり且つその積もまた(2, 3, 7)のみを素因数とする数が存在するか？というと、無いとは言い切れないが恐らく無い。だが、無いことを証明するのは極めて困難なことだろう。
なお、「wikipedi曰く、12回掛け算できる数は 10^20000 以上の場所にいるらしいですよ！」（原文ママ）などと誤った情報を拡散してる人が居たりするが、存在が確定している訳では決してないのでご注意を。
まとめ
どうにか大人としての体面は保つことができた。使用言語が python かどうか、なんてのも全くもってどうでもいい。
とはいえ、元ツイートに興味を示した大人たちの大半より件の12歳の方が上手くやったのは間違いない。実に素晴らしいことだと思う。
巷では 500桁で25秒なんて御仁も現れたので、もう自分の出る幕は無いな。という訳でおしまい。