- 1 -
1 から 1000 までの整数の中で、約数の数が
最も多い数字の求め方
０．はじめに
このファイルは、「あべしん」がmixi 内で一部に公開した『第 14 回勝抜杯』の予選奮戦 記「弱くても解けます」を改訂してまとめたものである。 主な変更内容は以下の通り。 ・mixi 内の奮戦記で示した解法を、ノーカットで解く ・その他、一部追記１．問題
『第14 回勝抜杯（2014 年 4 月 26 日開催）』の予選の問題番号 17 の問題を覚えているで しょうか？ 「1 から 1000 までの整数のなかで、約数の数が最も多い数字は何？」 一見すると、ただの面倒な計算問題と思う人もいるかと思いますが、この問題は非常に 奥が深いです。「そもそもどうやって求めるのか？」と思う人も多いと思うので、比較的 簡単にできる求め方を紹介しようと思います。２．答えを求める前の基礎知識
約数の数を求める前に、解りがいいように以下の説明を行う。 ２－１．約数の数の求め方 約数の数は素因数分解を行い、以下の式で求めることができる。 約数の数＝（素因数2 の個数+1）×（素因数 3 の個数+1）×（素因数 5 の個数+1）× （素因数7 の個数+1）×（素因数 11 の個数+1）×・・・- 2 - 例えば、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）である。 ２－２．『天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 の方が大きいことがわかる。従って、チームポイントの大小は正解 者数の大小だけでは判別できないため注意が必要である。
- 3 -
３．解法
「２－２．『天 by 天 by 天』ルール」を基に考えると、「正解者数」を「素因数の種類」、 「チーム正解数」を「素因数分解した時の素因数の個数」とみなして考えることができる。 素因数の種類を多くすれば約数の数が多くなる可能性が高いと考えられるので、そこを 基準に計算をスタートする。 結論を先に述べるが、1000 以下という条件では、素因数は最大で 4 種類しか持てない。 素因数を5 種類持つ自然数の最小値は 2×3×5×7×11=2310 となる。このことから、素因数を5 種類持つことはできないことは明らかであるため、 素因数を 4 種類持つ整数で約数の数が最も多くなる値を求める所から計算を始める。 ①素因数を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 ずつ倍々しているだけなので比較的 容易である。括弧外の数字は、約数の数が多そうな値の解りがいいように素因数分解した ものを表記している。- 4 - 以上の計算から、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 種類以下の事象も同様に計算して求める。 ②素因数を3 種類持つ整数の場合 素因数を3 種類持つ自然数の最小値は 2×3×5=30 である。
- 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)×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 の約数の数は
- 6 - （素因数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 である。 ③素因数を2 種類持つ整数の場合 素因数を2 種類持つ自然数の最小値は 2×3=6 である。
- 7 - この 6 をベースとして素因数を掛けていき、約数を多くすることを考えたいが、①、② のようにしらみつぶしに求めると時間がかかるため、ベース値に掛けることができる値の 最大値を先に求める。これを求めると、 1000÷6=166.66・・・ であるため、ベース値6 に掛けることができる値の最大値は 166 である。1 から 166 の 整数の中で、素因数を2 と 3 のみを使用するという条件で約数の数が最大になる数字は （2×3）×（2×3）×2×2=144 である。 各々の素因数の個数を万遍（まんべん）なく多くすることで、約数の数を多くすること が可能であることが「２－１．約数の数の求め方」から明らかである。この場合、ベース 値に素因数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 個である。
- 8 - ④素因数を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 から 1000 までの整数のなかで、約数の数が最も多い数字は 何？」という問いに対する正答は「840」である。
４．補足（高度合成数）
「１．問題」で示した問題文は、次のように言い換えることができる。 「1 から 1000 までの整数のなかで、最も大きい高度合成数は何？」 「高度合成数」とは、自身より小さい自然数の中に、約数の数が同じ、あるいは多い値 が存在しない数のことである。例えば、6 の約数は 1,2,3,6 の 4 個あるが、6 より小さい自 然数の中に約数の数が4 個以上のものは存在しないため、6 は高度合成数である。自身が頒布した記録集『Theory Of Quiz Games # Report』（2012 年 12 月初版）の 32 ページに、高度合成数に関する多答問題が掲載されているので、記録集をお持ちの方は ご覧下さい。
- 9 - 間、1 時間は「60」分、平角は「180」度、1 周は「360」度などなど・・・。鍵括弧で示 した値は全て高度合成数である。高度合成数は約数の数が多いため、整数で割り算をした 時に割り切れる可能性が高く計算が比較的容易である、という性質がある。 また、「高度合成数」を応用したものも身近な所に存在する。例えば、12 ダースを 1 とす る単位「グロス（12×12=144）」もその一つと推測することができる。「144」は高度合成 数ではないが、高度合成数「12」を 2 回掛けているため、必然的に約数の数も多くなる（144 の約数の数は15 個であり、144 以下で最も大きい高度合成数 120 の約数の数は 16 個なの で、144 の約数の数が多いことがわかる）。このように、生活に根付いた数字はただ何とな く決められたものではなく、裏付けがあるものだと言える。皆さんも、身近な数字に興味 を持ってみてはいかがでしょうか？ 2014 年 5 月 17 日（土）記 あべしん ＜以下、余白＞
