100！を素因数分解すると2^a、3^b、5^c、

質問

100！を素因数分解すると2^a、3^b、5^c、7^16、11^9、13^7…となる。a,b,cの値を求めよ。

という数A 整数の問題です。
画像は解答なのですが、何をしているのかわかりません。なぜ素因数の数?を調べるのですか？重複しないのですか？

回答No.3

staratras · ベストアンサー

素因数分解をした際に、2が含まれるのは偶数だけですから偶数を2,4,6,8,10,…90,92,94,96,98,100まで並べて、次ぎ次ぎに2で割っていくことを考えます。
2で割れなくなったら(商が奇数になったらそこで終わります）

そうすると下のようになります。最初は偶数だから当然全部割れて、この段階で2が50個ありました。次に割る際には、1つおきにしか割れません（2^2=4の倍数）のでこの段階で2が25個得られます。次に2で割るとさらに一つおき(2^3 =8の倍数)にしか割れないので2が12個得られます。以下この操作を繰り返すと、最後まで残るのは64(=2^6)で6回割れます。

ここまでわかれば後は、下の図で右端の2の個数をたてにすべて加えれば2が97個得られることがわかります。つまり100!を素因数分解すると2^97が含まれることがわかります。あとは３，５について同様に計算するだけです。

回答No.2

178-tall

>…画像は解答なのですが、何をしているのかわかりません。なぜ素因数の数?を調べるのですか？重複しないのですか？

100！= 1*2*3*4* … *98*100 なので、100！の素因数分解の結果を知るには、左辺各数の素因数分解を想定して、各素数の累乗ごとに、その出現個数を網羅・累計せねばなりません。

添付図面では、1 から 100 までの各数について「素因数の累乗ごとに、その出現個数を網羅探索 (exhaust search) 」している。
たとえば 2^3 なら、「2 の倍数」で 1 回、「2^2 の倍数」で 1 回、「2^3 の倍数」で 1 回、計 3 回カウントしており、過不足なしの「探索」になっている。

回答No.1

tmppassenger

要は、例えば100!が2で何回割れるかを調べたい訳ですが：

今、正整数nが2で割り切れる回数をφ(n)とします。つまり、φ(1) = 0, φ(2) = 1, φ(3) = 0, φ(4) = 2, φ(5) = 0, φ(6) = 1, φ(7) = 0, φ(8) = 3, .... とします。この時、φ(100!) = Σ[1≦n≦100] φ(n)となるのはいいですか？つまり、100!は1から100までの積ですから、1から100までのそれぞれの整数nが2で割り切れる回数の合計が、100! が 2で割り切れる回数になります。ここまではいいでしょう。

で、問題にある通り、100以下の整数nに関しては、φ(n)≦6であることから、今100以下でφ(n) = kとなるnの数をg(k)としますと、 φ(100!) = Σ[1≦n≦100] φ(n) = Σ[ 1≦k≦ 6] k * g(k) ( = 1 * g(1) + 2 * g(2) + 3 * g(3) + 4 * g(4) + 5 * g(5) + 6 * g(6) ) となります。

で、各kに対し、100以下でφ(n) = kとなる正整数nの数 g(k)はいくつか？が分かればよい。で、例えばφ(n) = 1、つまり 100以下の整数で、2で「ちょうど」1回割り切れる整数は何かを考えると、これは
『2^1 = 2では割り切れるが、 2^2 = 4では割り切れない』整数 <===== ここの考え
を考えればよい。つまり、2の倍数ではあるが、4の倍数ではない整数nが、φ(n) = 1となります。で、実数xの整数部分（つまり小数部分を切り捨てたもの）を[x]と書くと、従って g(1) は100以下の2の倍数の数から4の倍数の数を引いたもの、つまり g(1) = [100 / 2] - [ 100 / 4] となります。

同様に、一般に 100以下で、φ(n) = kとなる整数 n、つまり2^nでは割り切れるが2^{n+1}では割り切れない整数の数 g(k) は、g(k) = [ 100 / (2^k) ] - [ 100 / (2^(k+1) ] です。

従って、
φ(100!) = Σ[1≦n≦100] φ(n) = Σ[ 1≦k≦ 6] k * g(k) = Σ[ 1≦k≦ 6] k * { [ 100 / (2^k) ] - [ 100 / (2^(k+1)) ] } ですが、一番最後の式をうまく変形すれば、これは

Σ[ 1≦k≦ 6] k * { [ 100 / (2^k) ] - [ 100 / (2^(k+1)) ] }
= Σ[ 1≦k≦ 6] k * [ 100 / (2^k) ] - Σ[ 1≦k≦ 6] k * [ 100 / (2^(k+1)) ]
= Σ[ 1≦k≦ 6] k * [ 100 / (2^k) ] - Σ[ 2≦k≦ 7] (k-1) * [ 100 / (2^k) ]
<==== この式変形に注意
= Σ[ 1≦k≦ 6] k * [ 100 / (2^k) ] - Σ[ 1≦k≦ 6] (k-1) * [ 100 / (2^k) ] - (7-1) * [ 100 / (2^7)]
<===== k=1の時k-1=0だから、後のΣはk=1から初めて良い。 後、k=7の場合を分離
= Σ[ 1≦k≦ 6] (k-(k-1)) * [ 100 / (2^k) ]
<====== [ 100 / (2^7)] = 0に注意
= Σ[ 1≦k≦ 6] [ 100 / (2^k) ]

となって、見事解説と同じ式になります。

で、ここまでかなり丁寧に記しましたが、質問の「重複しないのですか？ 」という問に対しては、 <===== ここの考え という所と <==== この式変形に注意 という所を見てみると、実は解説の方法でその「重複することをうまく利用している」ということが分ります。

つまり、最初の方の式に戻って、
φ(100!) = Σ[1≦n≦100] φ(n) = Σ[ 1≦k≦ 6] k * g(k)
という式を考えると、解説の方法では、例えば φ(n) = 3、つまり2で ちょうど3回割り切れる数は、「2の倍数」「4の倍数」「8の倍数」でちょうど「3回、1足される」ので、つじつまがあっているのです。