1 から 1000 までの整数の中で約数の数が最も多い数字の求め方 0. はじめにこのファイルはあべしんが mixi 内で一部に公開した第 14 回勝抜杯の予選奮戦記弱くても解けますを改訂してまとめたものである主な変更内容は以下の通り mixi 内の奮戦記で示した解法をノーカット

Size: px

Start display at page:

Download "1 から 1000 までの整数の中で約数の数が最も多い数字の求め方 0. はじめにこのファイルはあべしんが mixi 内で一部に公開した第 14 回勝抜杯の予選奮戦記弱くても解けますを改訂してまとめたものである主な変更内容は以下の通り mixi 内の奮戦記で示した解法をノーカット"

はるまさしろみず
5 years ago
Views:

1 1 から 1000 までの整数の中で約数の数が最も多い数字の求め方 0. はじめにこのファイルはあべしんが mixi 内で一部に公開した第 14 回勝抜杯の予選奮戦記弱くても解けますを改訂してまとめたもの主な変更内容は以下の通り mixi 内の奮戦記で示した解法をノーカットで解くその他一部追記 1. 問題第 14 回勝抜杯 (2014 年 4 月 26 日開催 ) の予選の問題番号 17 の問題を覚えているでしょうか? 1 から 1000 までの整数のなかで約数の数が最も多い数字は何? 一見するとただの面倒な計算問題と思う人もいるかと思いますがこの問題は非常に奥が深いですそもそもどうやって求めるのか? と思う人も多いと思うので比較的簡単にできる求め方を紹介しようと思います 2. 答えを求める前の基礎知識約数の数を求める前に解りがいいように以下の説明を行う 2-1. 約数の数の求め方約数の数は素因数分解を行い以下の式で求めることができる約数の数 =( 素因数 2 の個数 +1) ( 素因数 3 の個数 +1) ( 素因数 5 の個数 +1) ( 素因数 7 の個数 +1) ( 素因数 11 の個数 +1) - 1 -

2 例えば 20 を素因数分解すると 20=2 2 5 となるこの場合素因数 2 の個数 =2 素因数 5 の個数 =1 それ以外の素因数の個数 =0 これを約数の数を求める式に代入すると (2+1) (0+1) (1+1) (0+1) (0+1) = =6 であるため 20 の約数の数は 6 個 (1,2,4,5,10,20) 2-2. 天 by 天 by 天ルール天 by 天 by 天とはクイズサークルによる団体戦天シリーズで行われるルールのひとつ全員 1 ポイント持った状態でスタートし早押しに正解すると正解者に 1 ポイントが加算されるチームポイントはメンバーのポイントを全て掛けた値になり先に 1000 以上になったチームが勝利というルール ( 誤答ペナルティなどの詳細なルールについては割愛する ) このルールの特徴はチーム正解数が同じでも正解者数が多い方がチームポイントが多くなるということ例えばチーム正解数が 3 の場合チームポイントは以下の 3 通りが考えられる ( 計算の簡略化のためチームメンバーは 3 人として考える ) パターン 1: 4 1 1=4 パターン 2: 3 2 1=6 パターン 3: 2 2 2=8 ただし正解者数が多くてもチーム正解数次第では必ずしもチームポイントが上になるとは限らない例えばチーム正解数が 4 の場合正解者数が 2 人の場合でもチームポイントは以下の 2 通りのパターンが考えられるパターン 4: 3 3 1=9 パターン 5: 4 2 1=8 この場合正解者数はパターン 3(3 人 ) の方がパターン 4(2 人 ) より多いがチームポイントはパターン 4 の方が大きいことがわかる従ってチームポイントの大小は正解者数の大小だけでは判別できないため注意が必要 - 2 -

3 3. 解法 2-2. 天 by 天 by 天ルールを基に考えると正解者数を素因数の種類チーム正解数を素因数分解した時の素因数の個数とみなして考えることができる素因数の種類を多くすれば約数の数が多くなる可能性が高いと考えられるのでそこを基準に計算をスタートする結論を先に述べるが 1000 以下という条件では素因数は最大で 4 種類しか持てない素因数を 5 種類持つ自然数の最小値は =2310 となるこのことから素因数を 5 種類持つことはできないことは明らかであるため素因数を 4 種類持つ整数で約数の数が最も多くなる値を求める所から計算を始める 1 素因数を 4 種類持つ整数の場合素因数を 4 種類持つ整数の最小値は =210 この 210 をベースとして素因数を掛けていき約数を多くすることを考えると以下の通りになる ( ) 2=420 ( ) 3=630 ( ) 2 2=840 ( ) 5=1050 この時点で 1000 を超えているため以降の計算は不要 ( ) 2 3=1260 ( ) 7=1470 : : 計算が面倒かと思うかもしれないがベース値を 1 ずつ倍々しているだけなので比較的容易括弧外の数字は約数の数が多そうな値の解りがいいように素因数分解したものを表記している - 3 -

4 以上の計算から 1000 以下という条件で 210 をベースとした時に約数の数が最も多くなる値は素因数 2 を 2 個追加している 840 同様の計算を行う 210 に次いで異なる素因数を 4 種類持つ小さい値は =330 この 330 をベースとして素因数の個数を増やすことを考えたいが先に求めた 840 はベースとなる値 210 から 4 倍 ( 素因数 2 を 2 個追加 ) しているため少なくとも 840 と約数の数を同じにするためには 4 倍しなければならないしかし 330 を 4 倍すると 1000 を超える (1320) ため 330 をベースにして約数を増やすことはできないよって 4 種類の素因数を持つ 1000 以下の値という条件で約数の数が最も多い値はを素因数分解すると 840= となるため 840 の約数の数は ( 素因数 2 の個数 +1) ( 素因数 3 の個数 +1) ( 素因数 5 の個数 +1) ( 素因数 7 の個数 +1)= =32 以上の計算から 840 の約数の数は 32 個なおここで求めた 840 が正解であるとは言い切れないこれは素因数が 4 種類持つもののみ計算しており素因数が 3 種類以下の整数の中に正答がある可能性があるため ( 素因数の種類を減らすと素因数分解した時の素因数の総数が多くなるため ) 従って素因数が 3 種類以下の事象も同様に計算して求める 2 素因数を 3 種類持つ整数の場合素因数を 3 種類持つ自然数の最小値は 2 3 5=30-4 -

5 この 30 をベースとして素因数を掛けていき約数を多くすることを考えると以下の通りになる (2 3 5) 2=60 (2 3 5) 3=90 (2 3 5) 2 2=120 (2 3 5) 5=150 (2 3 5) 2 3=180 (2 3 5) 7=210 素因数を 4 種類使用することになるため除外以下素因数を 4 種類使用する計算は除外する (2 3 5) 2 2 2=240( 括弧外の乗算 :8) (2 3 5) 3 3=270( 括弧外の乗算 :9) (2 3 5) 2 5=300( 括弧外の乗算 :10) (2 3 5) 2 2 3=360( 括弧外の乗算 :12) (2 3 5) 3 5=450( 括弧外の乗算 :15) (2 3 5) =480( 括弧外の乗算 :16) (2 3 5) 2 3 3=540( 括弧外の乗算 :18) (2 3 5) 2 2 5=600( 括弧外の乗算 :20) (2 3 5) =720( 括弧外の乗算 :24) (2 3 5) 5 5=750( 括弧外の乗算 :25) (2 3 5) 3 3 3=810( 括弧外の乗算 :27) (2 3 5) 2 3 5=900( 括弧外の乗算 :30) (2 3 5) =960( 括弧外の乗算 :32) (2 3 5) 2 17=1020( 括弧外の乗算 :34) 値が 1000 を超えるため計算終了上記の計算結果で約数の数が最大のものを一から求めるのは困難であるがベースとなる値は全て同じであるため括弧外の部分のみを比べれば自ずと約数の数が最も多い整数が絞り込める今回の場合 720( 素因数 2 を 3 個素因数 3 を 1 個追加 ) あるいは 900( 素因数 2 を 1 個素因数 3 を 1 個素因数 5 を 1 個追加 ) が約数の数が最も多いことが推測できるどちらの値の方が約数の数が多いかは今後の計算に重要であるため正確に求める 720 を素因数分解すると 720= となるため 720 の約数の数は - 5 -

6 ( 素因数 2 の個数 +1) ( 素因数 3 の個数 +1) ( 素因数 5 の個数 +1) =5 3 2=30 であるため 30 個 900 を素因数分解すると 900= となるため 900 の約数の数は ( 素因数 2 の個数 +1) ( 素因数 3 の個数 +1) ( 素因数 5 の個数 +1) =3 3 3=27 であるため 27 個以上の計算から 900 より 720 の方が約数の数が多い 720 の約数の数は 30 個 30 に次いで素因数を 3 種類持つ小さい値は 2 3 7=42 この 42 をベースとして素因数の個数を増やすことを考えたいが先に求めた 720 はベースとなる値 30 から 24 倍 ( 素因数 2 を 3 個素因数 3 を 1 個追加 ) しているため少なくとも 720 と約数の数を同じにするためには 24 倍しなければならないしかし 42 を 24 倍すると 1000 を超える (1008) ため 42 をベースにして約数を増やすことはできないよって 3 種類の素因数を持つ 1000 以下の値という条件で約数の数が最も多い値は素因数を 2 種類持つ整数の場合素因数を 2 種類持つ自然数の最小値は 2 3=6-6 -

7 この 6 をベースとして素因数を掛けていき約数を多くすることを考えたいが 1 2 のようにしらみつぶしに求めると時間がかかるためベース値に掛けることができる値の最大値を先に求めるこれを求めると = であるためベース値 6 に掛けることができる値の最大値はから 166 の整数の中で素因数を 2 と 3 のみを使用するという条件で約数の数が最大になる数字は (2 3) (2 3) 2 2=144 各々の素因数の個数を万遍 ( まんべん ) なく多くすることで約数の数を多くすることが可能であることが 2-1. 約数の数の求め方から明らかこの場合ベース値に素因数 2 を 4 個素因数 3 を 2 個追加している 864 が約数の数が最も多くなる 6 に次いで素因数を 2 種類持つ小さい値は 2 5=10 この 10 をベースとして素因数の個数を増やすことを考えたいが先に求めた 864 はベースとなる値 6 から 144 倍 ( 素因数 2 を 4 個素因数 3 を 2 個追加 ) しているため少なくとも 864 と約数の数を同じにするためには素因数 a を 4 個素因数 b を 2 個追加しなければならない a=2 b=5 とすると少なくともベース値を 400 倍しなければならないしかし 10 を 400 倍すると 1000 を超える (4000) ため 10 をベースにして約数を増やすことはできないよって 2 種類の素因数を持つ 1000 以下の値という条件で約数の数が最も多い値はを素因数分解すると 864= となるため 864 の約数の数は ( 素因数 2 の個数 +1) ( 素因数 3 の個数 +1) =6 4=24 以上の計算から 864 の約数の数は 24 個 - 7 -

8 4 素因数を 1 種類持つ整数の場合素因数を 1 種類のみ持つ整数で約数の数が最も多くなるのは素因数 2 のみを用いた値であるのは明確 1000 を超えない範囲で素因数 2 のみを最も多く用いた値が求める数字となるため 1000 以下で素因数 2 を最も多く用いる整数は =512(2 の 9 乗 ) なお 512 を素因数分解すると 512= となるため 512 の約数の数は ( 素因数 2 の個数 +1) =10 以上の計算から 512 の約数の数は 10 個 1~4 の計算結果より 1 から 1000 までの整数のなかで約数の数が最も多い数字は何? という問いに対する正答は補足 ( 高度合成数 ) 1. 問題で示した問題文は次のように言い換えることができる 1 から 1000 までの整数のなかで最も大きい高度合成数は何? 高度合成数とは自身より小さい自然数の中に約数の数が同じあるいは多い値が存在しない数のこと例えば 6 の約数は 1,2,3,6 の 4 個あるが 6 より小さい自然数の中に約数の数が 4 個以上のものは存在しないため 6 は高度合成数自身が頒布した記録集 Theory Of Quiz Games # Report (2012 年 12 月初版 ) の 32 ページに高度合成数に関する多答問題が掲載されているので記録集をお持ちの方はご覧下さい高度合成数は生活の中に非常に密接している 1 ダースは 12 個 1 日は 24 時 - 8 -

9 間 1 時間は 60 分平角は 180 度 1 周は 360 度などなど鍵括弧で示した値は全て高度合成数高度合成数は約数の数が多いため整数で割り算をした時に割り切れる可能性が高く計算が比較的容易であるという性質があるまた高度合成数を応用したものも身近な所に存在する例えば 12 ダースを 1 とする単位グロス (12 12=144) もその一つと推測することができる 144 は高度合成数ではないが高度合成数 12 を 2 回掛けているため必然的に約数の数も多くなる (144 の約数の数は 15 個であり 144 以下で最も大きい高度合成数 120 の約数の数は 16 個なので 144 の約数の数が多いことがわかる ) このように生活に根付いた数字はただ何となく決められたものではなく裏付けがあるものだと言える皆さんも身近な数字に興味を持ってみてはいかがでしょうか? 2014 年 5 月 17 日 ( 土 ) 記あべしん < 以下余白 > - 9 -

2013年度信州大・医系数学

2013年度信州大・医系数学 03 信州大学 ( 医系 ) 前期日程問題解答解説のページへ () 式 + + a a a3 を満たす自然数の組 ( a, a, a3) で, a a a3となるものをすべて求めよ () r を正の有理数とする式 r + + a a a を満たす自然数の組 ( a, a, a3) で, 3 a a a3となるものは有限個しかないことを証明せよただし, そのような組が存在しない場合は 0 個とし,