トップ > 大学入試（日本） > 100桁の自然数で2と5以外の素因数をもたないものの個数 / 2017 京都大学・文系第2問

100桁の自然数で2と5以外の素因数をもたないものの個数 / 2017 京都大学・文系第2問

大学入試（日本） 京都大学

問題

次の問いに答えよ。ただし， 0.3010<\log_{10} 2<0.3011 であることは用いてよい。

(1)　100 桁以下の自然数で，2 以外の素因数をもたないものの個数を求めよ。

(2)　100 桁の自然数で，2 と 5 以外の素因数をもたないものの個数を求めよ。

解説の pdf も作りました。きれいなレイアウトで読みたい方はこちらをどうぞ。

drive.google.com

解答・解説

(1)について

2^n が 100 桁以下の条件は 2^n<10^{100} です。
\log_{10} をとると n\log_{10} 2<100 になって

0\leqq n<\frac{100}{\log_{10} 2}

0.3010<\log_{10} 2<0.3011 から右辺の近似値がわかります。

\frac{100}{0.3011}=332.116\cdots<\frac{100}{\log_{10} 2}<\frac{100}{0.3010}=332.226\cdots

0\leqq n\leqq 332 より答えは 332-0+1=333 個です。

(2)について

2^p 5^q の形の数で 100 桁のものを数えます。

p=q のものは 10^{99}\leqq 2^p 5^p=10^p<10^{100} より p=q=99 の 1 個。

p>q のものは q=k, p=k+p' とおくと次のように書けます。

2^p 5^q=2^{p'}\cdot 10^k\quad (p'\geqq 1,\, k\geqq 0)

これは素因数に 2 だけをもつ 100 桁以下の自然数に 10 を 0 回以上かけたものです。

p< q のものも同様です。 p=k, q=k+q' とおきます。

2^p 5^q=5^{q'}\cdot 10^k\quad (q'\geqq 1,\, k\geqq 0)

これは素因数に 5 だけをもつ 100 桁以下の自然数に 10 を 0 回以上かけたものです。

これらの数にダブリはありませんが， p'=0 と q'=0 の数も含めてあえてダブらせた方が(1)とつながりやすく，数えやすくなります。

  • 2^p の形の数で n 桁のものが a_n 個あるとする。これらを 10^{100-n} 倍すると 100 桁になる。
  • 5^q の形の数で n 桁のものが b_n 個あるとする。これらを 10^{100-n} 倍すると 100 桁になる。

求める個数を N とおきます。
a_1, b_1 は 2^0=5^0=1 を含めて数えていて，これは上の例の p=q=99 のケースに対応することに注意してダブリを除きます。

\begin{align*}
N &=1+\left(\sum_{k=1}^{100} a_k-1\right)+\left(\sum_{k=1}^{100} b_k-1\right)\\
&=\sum_{k=1}^{100} a_k+\sum_{k=1}^{100} b_k-1
\end{align*}

\sum_{k=1}^{100} a_k=333 は(1)で求めました。

\sum_{k=1}^{100} b_k も同じ方法で求められます。

5^q<10^{100} とおくと

0\leqq q< \frac{100}{\log_{10} 5}=\frac{100}{1-\log_{10} 2}

0.3010< \log_{10} 2< 0.3011 から frac{100}{1-\log_{10} 2}=143.0\cdots がわかるので

0\leqq q\leqq 143\quad \therefore \sum_{k=1}^{100} b_k=143-0+1=144

求める個数は 333+144-1=476 個です。


variee.hatenablog.com