まひろ量子のハックログ

プログラミングや機械学習などの知識を記録・共有します

【数学パズル】末尾に同じ数が777個連続する階乗は存在するか

f:id:twx:20190317183144p:plain
画像提供:https://human-illustration.com/01-emotion-picture/043-free-silhouette.html

先日、いろんな数の階乗について調べていて「とある面白い性質」に気づいたので数学の問題にしてみました。難易度的には高校数学ですが、中学生でも鋭い子なら解けるかと思います。制限時間10分ほどで考えてみてください。なお、中学生向けに補足しておくと「階乗」というのは「\( 1 \times 2 \times 3 \times 4 \times 5 \)」のように1個ずつ階段のように数を掛け算していく計算のことです。この場合、1から5までの階段を掛けているので「5の階乗」と言い、「 \( 5!\) 」と書きます。

問題

任意の自然数 \(n\) に対して、「 \(n\) の1桁目から、同一の数が最も多く連続するのは\( f(n) \)桁目までである」という条件を満たす関数\( f(n) \)を定義する。 例えば、

$$ f(1234) = 1\\ f(12344) = 2\\ f(123444) = 3 $$

である。

このとき、

$$ f(N!) = 777 $$

となる自然数 \(N\) は存在するか。

解答

以下に解答を載せます。自力で解きたい方はスクロールするのを我慢してください。













まず、色々な数の階乗を見てみましょう。

N N!
1 1
2 2
3 6
4 24
5 120
6 720
7 5040
8 40320
9 362880
10 3628800
11 39916800
12 479001600
13 6227020800
14 87178291200
15 1307674368000
16 20922789888000
17 355687428096000
18 6402373705728000
19 121645100408832000
20 2432902008176640000
21 51090942171709440000
22 1124000727777607680000
23 25852016738884976640000
24 620448401733239439360000
25 15511210043330985984000000
26 403291461126605635584000000
27 10888869450418352160768000000
28 304888344611713860501504000000
29 8841761993739701954543616000000
30 265252859812191058636308480000000
31 8222838654177922817725562880000000
32 263130836933693530167218012160000000
33 8683317618811886495518194401280000000
34 295232799039604140847618609643520000000
35 10333147966386144929666651337523200000000
36 371993326789901217467999448150835200000000
37 13763753091226345046315979581580902400000000
38 523022617466601111760007224100074291200000000
39 20397882081197443358640281739902897356800000000
40 815915283247897734345611269596115894272000000000
41 33452526613163807108170062053440751665152000000000
42 1405006117752879898543142606244511569936384000000000
43 60415263063373835637355132068513997507264512000000000
44 2658271574788448768043625811014615890319638528000000000
45 119622220865480194561963161495657715064383733760000000000

\(5!\) 以降は全て、ゼロが末尾に連続しています。これは、\(5!\) 以降の数は必ず \(10\) を因数とした因数分解が可能であるからです。

具体的に言うと、\( 420 = 42 \times 10 \) のように10を因数に1個含む数は末尾に0が1個並びます。また、\( 4200 = 42 \times 10 \times 10 \) のように10を因数に2個含む数は末尾に0が2個並びます。

更に、もうちょっと踏み込んで考えてみます。\( 10 \) を素因数分解すると \( 2 \times 5 \) なので、「ある数の因数に \( 10 \) を何個含むことができるか」という問いは「ある数を素因数分解したときに2と5のペアが何組含まれているか」という問いと同じであることがわかります。また、階乗というのは「 \( 1 \times 2 \times 3 \times 4 \times 5 \times \cdots \times N \) 」のように1から \(N\) に至るまでの全ての自然数を因数に持っています。すると、階乗の因数には2が大量に存在していることがわかります。なぜなら、「 \( 1 \times 2 \times 3 \times 4 \times 5 \times \cdots \times N \) 」の各掛け算のうち2回に1回は2の倍数が登場するためです。同様に、階乗の因数には5もたくさん存在していますが、2ほどは多くないこともわかります。 「 \( 1 \times 2 \times 3 \times 4 \times 5 \times \cdots \times N \) 」の各掛け算のうち5の倍数が登場するのは5回に1回であるためです。

そのため、素因数分解して2と5のペアを作るときに、「5が余っているのに2が足りない…」と2の不足を心配する必要はないということがわかります。実際は「2が余っているのに5が足りない…」となるわけです。したがって、「階乗を素因数分解したときに2と5のペアが何組含まれているか」という問いは、「階乗を素因数分解したときに5が何個含まれているか」という問いと同じであることがわかります。

では、\( N! \) を素因数分解したときに \( 5 \) が幾つ含まれているのかを考えていきます。先ほど述べたように、「 \( 1 \times 2 \times 3 \times 4 \times 5 \times \cdots \times N \) 」の各掛け算のうち5の倍数が登場するのは5回に1回ですので、\( N \) を5で割ったときの商を計算すれば良さそうです。しかし、もう少し注意深く考えてみると、「 \( 1 \times 2 \times 3 \times 4 \times 5 \times \cdots \times N \) 」の各掛け算のうち25回に1回の頻度で25の倍数が登場します。25の倍数は素因数として5を2つ含んでいるため、これもカウントしてあげなくてはなりません。同様に、125回に1回の頻度で \( 5^{3} \) の倍数、625回に1回の頻度で \( 5^{4} \) の倍数が登場するため、これらもカウントしていきます。

結局、Nが5以上のときは、\( f(N!) \) つまり「 \( N! \) を素因数分解したときに \( 5 \) が幾つ含まれているのか」という問いの答えは、以下の計算式で求めることができます。

$$ f(N!) = \left[ \frac{ N }{ 5 } \right] + \left[ \frac{ N }{ 5^{2} } \right] + \left[ \frac{ N }{ 5^{3} } \right] + \left[ \frac{ N }{ 5^{4} } \right] + \cdots $$

ただし、ここでは、\( \left[ Z \right] \) は \( Z \) を超えない最大の整数(整数部分)を表します。 この和を見ると色々な性質がわかってきます。たとえば、\( f(N!) \geq f((N-1)!) \) ということがわかります。この不等式は、上述の右辺同士を比較してみるとすぐに得られます。・・・(1)

この和の計算方法について考えてみます。 もし第一項が100ならNは500〜504です。(もしNが505以上なら第一項は101以上になってしまいますし、もしNが499以下なら第一項は99になってしまいますので。) したがって、第二項は \( 500/5^{2} = 20 \) と計算可能です。同様に、第三項は \( 500/5^{3} = 4 \) 、第四項以降はゼロになります。以上の方法で、和は \( 100 + 20 + 4 = 124 \)と計算できることがわかります。

第一項は第二項以降に比べて比較的大きいため、\( f(N!) \) の値は第一項とかなり近いということがわかります。実際、上の例では第一項が100のときに \( f(N!) = 124 \) でした。

以上を踏まえて問題文を見てみましょう。

$$ f(N!) = 777 $$

を満たす \( N \) の値に、おおよその見当をつけていきます。

和の第一項を625とすると、第二項は125、第三項は25、第四項は5、第五項は1となり、\( f(N!) = 625 + 125 + 25 + 5 + 1 = 781 \) となります。言い換えると、素因数に5が781個含まれているということになります。目的の777個と比べると少しだけ多いですね。では、少しだけ素因数の5の個数を減らして777個にできるかどうかを考えてみます。さきほどのNの値は3125〜3129でした(第一項 \( 625 \times 5 = 3125 \) であるため)。このNから1だけ小さい \( N=3124 \)を考えてみます。計算すると、\( f(3124!) = 624 + 124 + 24 + 4 = 776 \)となります。

以上から、

$$ f(3125!) = 781\\ f(3124!) = 776 $$

となりました。 ここで、不等式(1)より、\( f(N!) \) は、\( f(N!) \geq f((N-1)!) \) という性質があるため、N>3125の範囲に\( f(N!) = 777 \) となるNはありませんし、N<3124の範囲にも\( f(N!) = 777 \) となるNはありません。

したがって、

$$ f(N!) = 777 $$

となる自然数 \(N\) は存在しないと言えます。

 

以上です。

本日は「末尾に同じ数が777個連続する階乗は存在するか」という問いを解いてみました。いかがでしたでしょうか。5以上の階乗には、末尾にゼロが連続するという面白い性質を使った問題でした。

良い記事だと思っていただいた方は、以下の「★+」ボタンのクリック、SNSでのシェア、「読者になる」ボタンのクリックをお願いします。 それではまたー!

Kozuko Mahiro's Hacklog ―― Copyright © 2018 Mahiro Kazuko