Evolton

岡山大学 2016年度 前期理系数学 第1問

p は素数とする.正の整数 n に対し,pd が n の約数となる整数 d(d≧0)のなかで最大のものを f(n) とする.このとき以下の問いに答えよ.

(1) p=3,n=(32)! のとき f(n) の値を求めよ.

(2) p=5,n=(52)! のとき f(n) の値を求めよ.

(3) m が正の整数で n=(pm)! のとき f(n) を求めよ.

難易度5/ 10計算量4/ 10目安14分

整数、数列 素因数分解、約数・倍数、和の計算

方針

n!に含まれる素数pの個数は,pの倍数,p2の倍数,p3の倍数,…を数えて足せばよい。(pm)!ではp,p2,…,pmの倍数だけを数えればよく,等比数列の和になる。

解答

(1)
32!=9!に含まれる素因数3の個数を数える。1,2,…,9の中で3の倍数は3個,9の倍数は1個である。したがってf(9!)=3+1=4である。

(2)
52!=25!に含まれる素因数5の個数を数える。1,2,…,25の中で5の倍数は5個,25の倍数は1個である。したがってf(25!)=5+1=6である。

(3)
n=(pm)!とする。(pm)!に含まれる素因数pの個数は,1,2,…,pmの中でpの倍数の個数,p2の倍数の個数,…,pmの倍数の個数を足したものである。

pkの倍数はpm−k個あるので,f(n)=pm−1+pm−2+⋯+p+1である。等比数列の和としてf(n)=pm−1p−1である。

別解

別解(段階ごとの漸化式)

方針

(1) (2) は (p2)! に含まれる p を,最初の1段と p の倍数に残る分に分けて数える。(3) は Em=f((pm)!) とおき,1 から pm までの p の倍数から1個ずつ p を取り出して Em の漸化式を作る。

解答

(1) 1,2,…,9 のうち3の倍数は 3,6,9 の3個で,それぞれ少なくとも1個の3をもつ。さらに 9=3⋅3 にはもう1個の3がある。したがってf(9!)=3+1=4.(2) 同様に,1,2,…,25 のうち5の倍数は5個で,25=5⋅5 にだけもう1個の5がある。よってf(25!)=5+1=6.(3) Em=f((pm)!) とおく。1 から pm までのうち,p の倍数はp,2p,3p,…,pm−1pの pm−1 個である。それぞれからまず1個ずつ p を取り出すと,残る積は (pm−1)! である。したがってEm=pm−1+Em−1.また E1=f(p!)=1 である。これを順に用いるとEm=pm−1+pm−2+⋯+p+1=pm−1p−1.ゆえにf(n)=pm−1p−1.

総評

難度5,計算量4。想定時間は14分程度。優先度は「必ず完答したい」。(1)(2) は倍数の個数を数える標準計算で,p2 の倍数をもう一度数えることが採点上の基本点になる。差がつく (3) では,pk の倍数が pm−k 個あることを明記するか,Em=pm−1+Em−1 を立てる。公式名だけで済ませず,なぜ重複して数えるかを一文で説明したい。

Evolton Pro

月額
2,480円(税込)
保存・印刷
公開過去問PDF・オーダーメイド問題集PDF
プランを確認・登録

冊子PDFで見る岡山大学の整数の問題で問題集を作る

出典: 岡山大学 2016年度 前期 理系数学 第1問(大学公式の問題PDF)。問題文はHTML表示のために再入力・数式組版しています。