最大値

質問

3＾nが300!の約数であるとき、整数nの最大値を求める方法がわかりません。

説明不足ですいません。
わかりません。
まず
3＾nが300!の約数であるときの意味が良くわかりません。

3＾nのnはいろんな数字が入ります。
しかしどんな数字を入れるのかわかりません。
約数も300!内だと沢山の数を調べないといけません。
しかし、そのなかの最大値を求めないといけないことはわかります。
お願いします。

回答No.6

shiga_3 · ベストアンサー

＃５＝＃２です。
＞どうして、3の倍数、９の倍数、27の倍数、81の倍数、243の倍数を全部＋のでしょうか？
＞ダブル数字はでてこないのでしょうか？

もちろん数字の個数としてはダブります。３の倍数の中にはもちろん９の倍数も含まれていますし、その中には27の倍数、81の倍数、243の倍数も含まれています。数字の個数は３の倍数の個数、つまり100個です。あとの33個、11個、3個、1個というのはすべてダブっています。

しかしここで求めようとしているのは、倍数の個数ではなくて、含まれている３の個数です。
数が大きすぎてわかりにくい時は、とりあえず小さい数で検証してみればわかります。
例えば１０！で２の個数について検証してみます。
１０！＝１０×９×８×７×６×５×４×３×２×１
　　　＝(５×２)×(３×３)×(２×２×２)×７×(３×２)×５×(２×２)×３×２×１
　　　＝７×５^２×３^４×２^８×１

ここで２の倍数は２、４、６、８、１０の５個です。個数は１０÷２＝５と出すことが出来ます。
しかし上の計算式を見ると「２^５」ではなくて「２^８」となっています。なぜだかわかりますか。
それは８が２×２×２、４が２×２と、２を余計に含んでいるためです。ここでは数えれば、８にあと２つ、４にあと１つ、合わせて３つで５＋３＝８と出せますが、数が多くなってくると一つ一つ数えていては大変です。そこで、８を４×２（(２×２)×２）と考えて、まず２を２つ含んでいる４の倍数の個数を１０÷４＝２（余り２）と出して、さらにもう一つ余計に２を含んでいる８の倍数の個数を１０÷８＝１（余り２）と出します。
つまり、４や８の中に含まれている２の数だけダブって個数をカウントすることで、１０！に含まれる２の個数を出すことができるというわけです。

以上の説明で分かりましたでしょうか。分からなければ補足してください。

あと、これはアドバイスですけど、追加質問をする時にはできるだけまとめてした方がいいですよ。
もちろん再質問の回答の中に分からないところがあって、その部分を質問するのは構わないのですが、元の質問に返ってまた別の質問となると、それだけ解決するまでに時間がかかることになります。回答してくれる人がすぐに答えを返してくれるといいですが、そうばかりとは限りません。そうすると解決が遅れ、その間にせっかく理解したことを忘れてしまう場合だってあります。
また、回答者の側からしてもまとめて質問してくれた方が、自分の回答を一応最後まで全部（一部ではなく）読んで理解しようと努力してくれている、というのが感じられて気持ちがいいです。進研ゼミなんかの通信添削と違って、回答者も人の子、気分が乗らなきゃほったらかし、というのもこういう掲示板ではありですから。今回は乗りかかった舟ですから、最後までとことんお付き合いするつもりですけど、今後質問される場合は考慮しておかれた方が良いと思います。

補足

なんども聞いてすいません。
＞ここでは数えれば、８にあと２つ、４にあと１つ、合わせて３つで５＋３＝８と出せますが、数が多くなってくると一つ一つ数えていては大変です。そこで、８を４×２（(２×２)×２）と考えて、まず２を２つ含んでいる４の倍数の個数を１０÷４＝２（余り２）と出して、さらにもう一つ余計に２を含んでいる８の倍数の個数を１０÷８＝１（余り２）と出します。
についてよくわかりません。
特に
＜８にあと２つ、４にあと１つ、合わせて３つで５＋３＝８と出せますが、数が多くなってくると一つ一つ数えていては大変です。そこで、８を４×２（(２×２)×２）と考えて、
それから、どうして余りがダブった数なのでしょうか？

回答No.8

eatern27

文字を使わないで,ですね。

先ほどと同じように３で割った商と、３の倍数の数を考えます。

Ｎ 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,・・・
商 0,0,1,1,1,2,2,2,3, 3, 3, 4, 4, 4, 5,・・・
数 0,0,1,1,1,2,2,2,3, 3, 3, 4, 4, 4, 5,・・・

ここで、「商」はＮ(一番上の数)を３で割ったときの商
「数」は１からＮ(一番上の数)までの３の倍数の数です。

(もしかしたら、上の表が歪んでいるかもしれないので、歪んでいたら,

一番上に、1,2,3,4,5・・・
その下に、↑を３で割った時の商
その下に、１から一番上の数までの3の倍数の数

を書いてみてください)

「商」と「数」の欄の数字の並びが見事に一致しているのが分かると思います。
おまけに、上のように考えれば,「余り」が関係ないことも分かるのではないでしょうか？

ここでは、3で割ったときの商,3の倍数の数のように"3"の場合しか見ていませんが,別に"3"ではなくて、"4"や"5"や"4640"でも成り立つことなんです。

回答No.7

eatern27

#6さんのおっしゃっている事は私にも分かりにくい(何となくは分かるのですが、上手く説明できない)ので、私なりに説明します。

１～２０までの「２の個数」(といっていいのか分かりませんが)がいくつなのか考えてみましょう。
(つまり、20!を素因数分解した時の2の指数部分を考える、ってことです)

　　　↓　↓　↓　↓
２　＝２
４　＝２×２
６　＝２　　　　　　　　×３
８　＝２×２×２
１０＝２　　　　　　　　×５
１２＝２×２　　　　　　×３
１４＝２　　　　　　　　×７
１６＝２×２×２×２
１８＝２　　　　　　　　×９
２０＝２×２　　　　　　×５

(図が歪んでたらすいません。↓は２のある列の上に書いたつもりです)

上に書いてある表(?)の"２"の数を数えればいいことは分かるでしょうか？
普通に数えてもいいですが、こんな風に考える事もできます。

１番左の↓の下に"２"がある物は２の倍数のみです。
以下同様に、２番目の下は４(=2^2)の倍数、３番目の下は８(=2^3)の倍数、４番目の下は16(=2^4)の倍数のみ、ですね。なので、

1番左の↓の下には"2"が２の倍数の数だけあります。
以下同様に、2番目の下には4の倍数の数、3番目の下には８の倍数の数、4番目の下には16の倍数の数だけある、ということです。

こんな風に考えると、1～20までの「2の個数」は
1～20までの「2の倍数の数」＋「４の倍数の数」＋「８の倍数の数」＋「１６の倍数の数」
に等しい事がわかると思います。

余談ですが、ここでは、「１６(=2^4)の倍数の数」までしか足していませんが、本来ならば、
「2^5の倍数の数」+「2^6の倍数の数」+・・・
も足すべきです。しかし、「2^5(=32)の倍数の数」以降が0である事は分かっている(事にしている)ので、途中までしか足していません。

この考え方を応用すれば、
＞どうして、3の倍数、９の倍数、27の倍数、81の倍数、243の倍数を全部＋のでしょうか？
＞ダブル数字はでてこないのでしょうか？
については解決できると思います。

＞それから、どうして余りがダブった数なのでしょうか？
「余り」ではなく、「商」ですね。
(ダブった数、ではなく、「4の倍数の数」などと考えてください）

具体例として、１～Ｎまでの３の倍数の数を考えます。
全ての自然数Ｎは、Ｎ＝３ｑ＋ｒ、(ｒ＝0,1,2)
と表す事ができ、このとき、Ｎを３で割ったときの商はｑ
１からＮまでの３の倍数の数は、3*1,3*2,・・・,3qのｑ個です。
よって、「１からＮまでの３の倍数の数」＝「Ｎを３で割ったときの商」となります。

(同じ様に考えれば１～Ｎまでの、ｐの倍数の数が、Ｎをｐで割った時の商に等しい事が分かると思います)

このような理由から、
＞４の倍数の個数を１０÷４＝２（余り２）と出して
＞８の倍数の個数を１０÷８＝１（余り２）と出します
などと１０を４(or８)で割った「商」を求めています。

かなり長くなってしまいましたが、分かったでしょうか？

お礼

Ｎを使うとよくわからないです。
できれば、数字で教えてくれませんか？
すいません。

補足

<
具体例として、１～Ｎまでの３の倍数の数を考えます。
全ての自然数Ｎは、Ｎ＝３ｑ＋ｒ、(ｒ＝0,1,2)
と表す事ができ、このとき、Ｎを３で割ったときの商はｑ
１からＮまでの３の倍数の数は、3*1,3*2,・・・,3qのｑ個です。
よって、「１からＮまでの３の倍数の数」＝「Ｎを３で割ったときの商」となります。

(同じ様に考えれば１～Ｎまでの、ｐの倍数の数が、Ｎをｐで割った時の商に等しい事が分かると思います)

このような理由から、
＞４の倍数の個数を１０÷４＝２（余り２）と出して
＞８の倍数の個数を１０÷８＝１（余り２）と出します
などと１０を４(or８)で割った「商」を求めています。

がよくわかりません。
商は必要で、余りは無視していいのですか？

回答No.5

shiga_3

＃２です。

＞90＝2×3^2×5で、（=3^2）は約数なのに、27（=3^3）は約数ではないのですか？

では「約数」とは何か、ということについて説明します。

1）「約数」とはある正の整数を余りがないように割り切れる正の整数のことを言います。
→例えば90の場合、9は90÷9＝10で余りが出ないので9は10の約数。8は90÷8＝11余り2で余りが出ますので8は90の約数ではありません。

2）1）は言い換えれば、ある正の整数をｎとする時に、ｎは同じく正の整数のｌ(エル)、ｍを使って、ｎ＝ｌ×ｍで表すことができるということです。
→例えば90＝9×10と表すことはできますが、8を使うと90＝8×11.25となり、ｍが小数になってしまいます。

ここまでで、90÷27＝3余り9（90＝27×3.333…）となりますので、27は90の約数ではないということは分かるかと思います。

さらに、2）をもう少し進めて、
3）ｎ＝ｌ×ｍのｌとｍが１またはそれ自身（ｌ、ｍ）以外の数で割ることができれば、ｎはさらに小さい数の積で表すことができます。そして、その小さい数が１またはそれ自身でしか割れなくなったときに、その数を素数と言い、元の数をその素数の積で表すことを素因数分解と言います。
→例えば90＝9×10ですが、9＝3×3（3^2）、10＝2×5ですから、90＝2×3^2×5と表すことができます。そして2,3,5はそれぞれ素数ですので、「90を素因数分解すると2×3^2×5になる」という言い方もできます。

4）素因数分解した結果を使って、元の数ｎの約数を求める場合、約数は１とｎ、そして素因数分解して出てきた素数自身、それからその素数を掛け合わせたものになります。
→例えば90の場合、1と90がまず約数。それから90＝2×3^2×5ですから2、3、5も約数。それから2、3、3、5の掛け算の組み合わせで、2×3(=6)、3×3(=9)、2×5(=10)、3×5(=15)、2×3×3(=18)、2×3×5(=30)、3×3×5(=45)（2×3×3×5=90は最初に出てきたので省きます）が約数となります。

ここで＃１の例に戻ると、3や9（=3×3）は90を素因数分解した結果出てきた2,3,3,5の組み合わせで求めることができるので90の約数、27（=3×3×3）はできませんので90の約数ではないということになります。

以上でお分かりでしょうか。すでにご存知のことも多かったと思いますが、基本的なところからの理解も大事だと思いましたので、できるだけ詳しく説明してみました。

補足

親切な説明ありがとうございます。
ほとんどわかって着ました。
しかし、一部部分がわかりません。
どうして、3の倍数、９の倍数、27の倍数、81の倍数、243の倍数を全部＋のでしょうか？

ダブル数字はでてこないのでしょうか？

回答No.4

cip

＃１です。
勘違いしていました。

回答No.3

kony0

#1さん
300!を素因数分解したときの3の個数は148個では？

回答No.2

shiga_3

「3＾nが300!の約数である」というのは、ｎに１、２、３・・・と入力していった時に、300!がその数で割り切れるということです。

言い換えれば、300！＝2^k×3^ｍ×・・・と表すことができますが、ｍ≧ｎの時、3＾nは300!の約数となります。
例えば
90＝2×3^2×5で、3や9（=3^2）は約数ですが、27（=3^3）は約数ではないことからも分かると思います。
そして整数nの最大値を求めよ、というのは、この３のべき乗の項（3^ｍ）のｍを求めよという問いに他なりません。

さて300！に含まれる３の数ですが、まず３の約数を並べてみます。
3,6,9,12,・・・,297,300
この個数は300÷3=100個になります。

ところが、この中には９の倍数も含まれています。9=3×3ですから、３の含まれている数を数えるためには、その分の個数を足してやらなけばいけません。
９の倍数の個数は300÷9=33余り3で33個になります。

さらにその中には２７（=3^3）の倍数も含まれています。同じく８１（=3^4）、２４３（=3^5）も含まれています。
それぞれの個数は計算して11、3、1個となります。

これらの個数を全て足し合わせたものが300！に含まれる３の個数になり、よって100＋33＋11＋3＋1＝148がｎの最大値ということになります。

補足

どうして、
90＝2×3^2×5で、3や9（=3^2）は約数なのに、
27（=3^3）は約数ではないのですか？

回答No.1

cip

「3^nが300!の約数である」ということは、300!が3^nで割り切れるということです。
つまり、3^n×○=300!
ならば、300!を素因数分解したとき、3がいくつあるかを調べればよいのではないでしょうか。

3の倍数というと、3,6,9,12,....,297,300
3でくくって、3×(1,2,3,....,99,100)
ここでの、1,2,3,...,99,100が3の個数そのものなので、全部足しましょう。

１から１００まで足したときの計算方法はいいですよね？ 最初と最後を足して個数をかけて２で割る。
５０５０ですね。

300!には3が5050個含まれています。
よって、n=5050 です。