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 -
例えば 20 を素因数分解すると 20=2 2 5 となる この場合 素因数 2 の個数 =2 素因数 5 の個数 =1 それ以外の素因数の個数 =0 これを約数の数を求める式に代入すると (2+1) (0+1) (1+1) (0+1) (0+1) =3 1 2 1 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. 解法 2-2. 天 by 天 by 天 ルール を基に考えると 正解者数 を 素因数の種類 チーム正解数 を 素因数分解した時の素因数の個数 とみなして考えることができる 素因数の種類を多くすれば約数の数が多くなる可能性が高いと考えられるので そこを基準に計算をスタートする 結論を先に述べるが 1000 以下という条件では 素因数は最大で 4 種類しか持てない 素因数を 5 種類持つ自然数の最小値は 2 3 5 7 11=2310 となる このことから 素因数を 5 種類持つことはできないことは明らかであるため 素因数を 4 種類持つ整数で約数の数が最も多くなる値を求める所から計算を始める 1 素因数を 4 種類持つ整数の場合 素因数を 4 種類持つ整数の最小値は 2 3 5 7=210 この 210 をベースとして素因数を掛けていき 約数を多くすることを考えると 以下の通りになる (2 3 5 7) 2=420 (2 3 5 7) 3=630 (2 3 5 7) 2 2=840 (2 3 5 7) 5=1050 この時点で 1000 を超えているため 以降の計算は不要 (2 3 5 7) 2 3=1260 (2 3 5 7) 7=1470 : : 計算が面倒かと思うかもしれないが ベース値を 1 ずつ倍々しているだけなので比較的 容易括弧外の数字は 約数の数が多そうな値の解りがいいように素因数分解した ものを表記している - 3 -
以上の計算から 1000 以下という条件で 210 をベースとした時に約数の数が最も多く なる値は 素因数 2 を 2 個追加している 840 同様の計算を行う 210 に次いで 異なる素因数を 4 種類持つ小さい値は 2 3 5 11=330 この 330 をベースとして素因数の個数を増やすことを考えたいが 先に求めた 840 は ベースとなる値 210 から 4 倍 ( 素因数 2 を 2 個追加 ) しているため 少なくとも 840 と約数の数を同じにするためには 4 倍しなければならない しかし 330 を 4 倍すると 1000 を超える (1320) ため 330 をベースにして約数を増やすことはできない よって 4 種類の素因数を持つ 1000 以下の値 という条件で約数の数が最も多い値は 840 840 を素因数分解すると 840=2 2 2 3 5 7 となるため 840 の約数の数は ( 素因数 2 の個数 +1) ( 素因数 3 の個数 +1) ( 素因数 5 の個数 +1) ( 素因数 7 の個数 +1)=4 2 2 2=32 以上の計算から 840 の約数の数は 32 個 なお ここで求めた 840 が正解であるとは言い切れない これは素因数が 4 種類持つもののみ計算しており 素因数が 3 種類以下の整数の中に正答がある可能性があるため ( 素因数の種類を減らすと 素因数分解した時の素因数の総数が多くなるため ) 従って 素因数が 3 種類以下の事象も同様に計算して求める 2 素因数を 3 種類持つ整数の場合 素因数を 3 種類持つ自然数の最小値は 2 3 5=30-4 -
この 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) 2 2 2 2=480( 括弧外の乗算 :16) (2 3 5) 2 3 3=540( 括弧外の乗算 :18) (2 3 5) 2 2 5=600( 括弧外の乗算 :20) (2 3 5) 2 2 2 3=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) 2 2 2 2 2=960( 括弧外の乗算 :32) (2 3 5) 2 17=1020( 括弧外の乗算 :34) 値が 1000 を超えるため計算終了 上記の計算結果で約数の数が最大のものを一から求めるのは困難であるが ベースとなる値は全て同じであるため 括弧外の部分のみを比べれば 自ずと約数の数が最も多い整数が絞り込める 今回の場合 720( 素因数 2 を 3 個 素因数 3 を 1 個追加 ) あるいは 900( 素因数 2 を 1 個 素因数 3 を 1 個 素因数 5 を 1 個追加 ) が約数の数が最も多いことが推測できる どちらの値の方が約数の数が多いかは今後の計算に重要であるため 正確に求める 720 を素因数分解すると 720=2 2 2 2 3 3 5 となるため 720 の約数の数は - 5 -
( 素因数 2 の個数 +1) ( 素因数 3 の個数 +1) ( 素因数 5 の個数 +1) =5 3 2=30 であるため 30 個 900 を素因数分解すると 900=2 2 3 3 5 5 となるため 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 以下の値 という条件で約数の数が最も多い値は 720 3 素因数を 2 種類持つ整数の場合 素因数を 2 種類持つ自然数の最小値は 2 3=6-6 -
この 6 をベースとして素因数を掛けていき 約数を多くすることを考えたいが 1 2 のようにしらみつぶしに求めると時間がかかるため ベース値に掛けることができる値の最大値を先に求める これを求めると 1000 6=166.66 であるため ベース値 6 に掛けることができる値の最大値は 166 1 から 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 を素因数分解すると 864=2 2 2 2 2 3 3 3 となるため 864 の約数の数は ( 素因数 2 の個数 +1) ( 素因数 3 の個数 +1) =6 4=24 以上の計算から 864 の約数の数は 24 個 - 7 -
4 素因数を 1 種類持つ整数の場合素因数を 1 種類のみ持つ整数で 約数の数が最も多くなるのは 素因数 2 のみを用いた値であるのは明確 1000 を超えない範囲で素因数 2 のみを最も多く用いた値が求める数字となるため 1000 以下で素因数 2 を最も多く用いる整数は 2 2 2 2 2 2 2 2 2=512(2 の 9 乗 ) なお 512 を素因数分解すると 512=2 2 2 2 2 2 2 2 2 となるため 512 の約数の数は ( 素因数 2 の個数 +1) =10 以上の計算から 512 の約数の数は 10 個 1~4 の計算結果より 1 から 1000 までの整数のなかで 約数の数が最も多い数字は 何? という問いに対する正答は 840 4. 補足 ( 高度合成数 ) 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 -
間 1 時間は 60 分 平角は 180 度 1 周は 360 度などなど 鍵括弧で示 した値は全て高度合成数高度合成数は約数の数が多いため 整数で割り算をした 時に割り切れる可能性が高く計算が比較的容易である という性質がある また 高度合成数 を応用したものも身近な所に存在する 例えば 12 ダースを 1 とする単位 グロス (12 12=144) もその一つと推測することができる 144 は高度合成数ではないが 高度合成数 12 を 2 回掛けているため 必然的に約数の数も多くなる (144 の約数の数は 15 個であり 144 以下で最も大きい高度合成数 120 の約数の数は 16 個なので 144 の約数の数が多いことがわかる ) このように 生活に根付いた数字はただ何となく決められたものではなく 裏付けがあるものだと言える 皆さんも 身近な数字に興味を持ってみてはいかがでしょうか? 2014 年 5 月 17 日 ( 土 ) 記あべしん < 以下 余白 > - 9 -