約数の個数　　　　　　　　　　　　　　　 　　　　　　　　　　　　　　　

　当ＨＰがいつもお世話になっているＨＮ「ＧＡＩ」さんからの出題です。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（平成２５年８月１３日付け）

　約数について面白かったので調査してみました。

　約数の個数が１００個になる最小の数が４５３６０で、２００個になる最小の数は４９８９６０
でした。

　実際に、　４５３６０＝２⁴・３⁴・５・７　から、約数の個数は、　５・５・２・２＝１００
　　　　　　　４９８９６０＝２⁴・３⁴・５・７・１１　から、約数の個数は、　５・５・２・２・２＝２００

　また、約数として、１，２，３，４，５，６，７，８，９，１０を含む最小の数が２５２０で、同じく約
数として１，２，３，・・・，２０を含む最小の数は２３２７９２５６０でした。

　実際に、　１，２，３，４＝２²，５，６＝２・３，７，８＝２³，９＝３²，１０＝２・５　から、求める
最小の数は、　２³・３²・５・７＝２５２０　である。２３２７９２５６０も同様に求められる。

　では、約数の個数が３００個、４００個、５００個になる最小の数はそれぞれ何でしょう？

さらに、約数として１，２，３，・・・，１００を含む最小の数とは？























（答）　らすかるさんが考察されました。（平成２５年８月１３日付け）

　　300=2²・３・5² なので、約数の個数が300個になる最小の数は、2⁴・3⁴・5²・7・11=2494800
　　400=2⁴・5² なので、約数の個数が400個になる最小の数は、2⁴・3⁴・5・7・11・13=6486480
　　500=2²・5³ なので、約数の個数が500個になる最小の数は、2⁴・3⁴・5⁴・7・11=62370000

　約数に1〜100を含む最小の数は、

　2⁶＜100＜2⁷、3⁴＜100＜3⁵、5²＜100＜5³、7²＜100＜7³　から、2⁶、3⁴、5²、7²　および
素数　11、13、17、19、23、29、31、37、41、43、47、53、59、61、67、71、73、79、83、89、97
を含むので、

　2⁶・3⁴・5²・7²・11・13・17・19・23・29・31・37・41・43・47・53・59・61・67・71・73・79・83・89・97
=69720375229712477164533808935312303556800


　ＧＡＩ さんからのコメントです。（平成２５年８月１３日付け）

　実は拙いプログラムを作って、かなり時間をかけて答えを見つけていました。本当は約数
の個数が777個のものを探していたんですが、なかなか見つけられず、これは出題せずに
おりました。これに対するらすかるさんの解法を見させてもらい、目から鱗がとれる思いでし
た。任意の約数の個数を有する最小の数を直接探せる手段がはっきりと理解できました。

　777個の約数を持つ最小の数は、1252412463513600

　実際に、777＝３・７・３７　なので、求める最小の数は、２³⁶・３⁶・５²＝1252412463513600

　こんなに大きくなる数を闇雲に探そうとしていたこと自体無謀でした。プログラムに精通され
ているらすかるさんがコンピュータに頼らず、論理の組合せで考えられたことに改めて敬服し
ます。


　ＧＡＩ さんからの続報です。（平成２５年８月１６日付け）

　約数の個数がn個になる最小な数をN(n)として、n=１〜２００について求める操作を、なる
だけコンピュータで処理できるようにとプログラムの修正を繰り返しながら苦心して調べて
みました。

　なかなか自動的に一つのプログラムで処理しようと悪戦苦闘しましたが、（ほとんど一日
中）どうしてもうまく繋がらない部分が出てきて、その都度特定の行列を手動で構成しなが
ら作業を進めました。

　ふと気になって、オンライン整数列大辞典で検索してみたら、n=1〜1000の表が既に調査
されていました。（世界中では、どこかに誰かがいち早く調べ尽くしているものですね〜）

　プログラムする技能が不足しているので、かなり非効率なプログラムで調査していると思
います。また自動的にひとつの流れとしてプログラムが動くようにいつかしてみたいです。
どなたか、これを求めるプログラムを組むことをされたなら、そのプログラムを公開して頂
けませんでしょうか？


　らすかるさんからのコメントです。（平成２５年８月１６日付け）

　「約数の個数がn個になる最小の数」の数列は「A005179」です。プログラムでは指数の処
理をうまくやる必要がありますね。

　例えば、８＝２³ なので、２¹・３¹・５¹＝３０ が最小と判断しがちですが、実は、２³・３＝２４
が最小となります。

　また、４８０＝２⁵・３・５ において、組合せはいろいろ考えられます。

　5、3、2、2、2、2、2　と考えて、　２⁴・３²・５・７・１１・１３・１７

　5・2、3、2、2、2、2　と考えて、　 ２⁹・３²・５・７・１１・１３

　3・2、5、2、2、2、2　と考えて、　 ２⁵・３⁴・５・７・１１・１３

　これらは最小ではなく、

　5、2・2、3、2、2、2　と考えた　 ２⁴・３³・５²・７・１１・１３＝１０８１０８００

が最小になります。使用する素数の値の大きさによって組み合わせ方が変わるわけで、実

際にある程度の組合せについて計算して最小値を探さなければならないと思います。

　ｎ が小さければ（例えば、1,000,000 とか）素因数もそれほど多くはなりませんので、全部の
組合せについて計算するのが単純でいいですかね。