平成１２年１０月１５日

［約数の最大個数］

太郎さんは、学校で、ある自然数の約数の問題を扱っています。

（ここでは、約数は正の自然数としておきます。）

したがって、３６の約数の個数は　（２＋１）×（２＋１）＝９　　（個）

　また、３６の約数の和は、この表の中の９個の和だから、分配法則から、

（１＋２＋４）×（１＋３＋９）＝９１　　　（答）　

ここで、授業中に、生徒に出した問題を書いておきます。

問１：３６のこの約数の積を求めよ。

問２：３６以下で、３６との最大公約数が１である数の個数を求めよ。

問３：３６以下で、３６との最大公約数が１である数の和を求めよ。

　多くの読者の皆さんは、もうこの考え方はよくご存じでしょう。

そこで、新しい疑問を持ち始めました。１桁の自然数のとき、約数の最大個数は

６＝２×３　、８＝２^３から　４個が最大個数の約数を持ちます。では、

問題４：２桁の自然数のとき、約数の最大個数を持つ自然数を求めよ。

問題５：３桁の自然数のとき、約数の最大個数を持つ自然数を求めよ。

　以上から、４桁の場合も出題したいのですが、太郎さんは、まだ答を見いだしていません。

いつもお世話になっています。清川（kiyo）です。

解答　問題１　36^4*6=10077696　　　答え １００７７６９６ 。

問題２　36*(1-1/2)*(1-1/3)=12　　　答え １２個。

問題３　(1+35)*12/2=216　　　　　　 答え ２１６。

問題４　　60=2^2*3*5

　72=2^3*3^2

　84=2^2*3*7

　90=2*3^2*5

　96=2^5*3　　　　　　　　１２個

問題５　　840=2^3*3*5*7　　　　　　３２個

４桁の場合

7560=2^3*3^3*5*7

9240=2^3*3*5*7*11　　　　　　６４個

こんにちはch3coohです。記録に残る暑さだった夏も過ぎ ようやく涼しく（寒く？？）なってきましたね

Q1 : 2^9 x 3^9

Q2 : 12

1,5,7,11,13,17,19,23,25,29,31,35

Q3 : 216

Q4 : 12

60 = 2^2 x 3 x 5

72 = 2^3 x 3^2

84 = 2^2 x 3 x 7

90 = 2 x 3^2 x 5

96 = 2^5 x 3

Q5 : 32

840= 2^3 x 3^1 x 5 x 7

この後は

(64)

7560 = 2^3 x 3^3 x 5 x 7

9240 = 2^3 x 3 x 5 x 7 x 11

(128)

83160= 2^3 x 3^3 x 5 x 7 x 11

98280= 2^3 x 3^3 x 5 x 7 x 13

となっています。

3,4,5桁が各々2^5, 2^6, 2^7となっているので次は2^8かというとそうではなく240でした。

(Q4, Q5 はプログラムで探索しました。

この出力を参考までに添付すると)

6=(2^1)(3^1) : 4 : max !!

8=(2^3) : 4 : max !!

10=(2^1)(5^1) : 4 : max !!

12=(2^2)(3^1) : 6 : max !!

18=(2^1)(3^2) : 6 : max !!

20=(2^2)(5^1) : 6 : max !!

24=(2^3)(3^1) : 8 : max !!

30=(2^1)(3^1)(5^1) : 8 : max !!

36=(2^2)(3^2) : 9 : max !!

48=(2^4)(3^1) : 10 : max !!

60=(2^2)(3^1)(5^1) : 12 : max !!

72=(2^3)(3^2) : 12 : max !!

84=(2^2)(3^1)(7^1) : 12 : max !!

90=(2^1)(3^2)(5^1) : 12 : max !!

96=(2^5)(3^1) : 12 : max !!

108=(2^2)(3^3) : 12 : max !!

120=(2^3)(3^1)(5^1) : 16 : max !!

168=(2^3)(3^1)(7^1) : 16 : max !!

180=(2^2)(3^2)(5^1) : 18 : max !!

240=(2^4)(3^1)(5^1) : 20 : max !!

336=(2^4)(3^1)(7^1) : 20 : max !!

360=(2^3)(3^2)(5^1) : 24 : max !!

420=(2^2)(3^1)(5^1)(7^1) : 24 : max !!

480=(2^5)(3^1)(5^1) : 24 : max !!

504=(2^3)(3^2)(7^1) : 24 : max !!

540=(2^2)(3^3)(5^1) : 24 : max !!

600=(2^3)(3^1)(5^2) : 24 : max !!

630=(2^1)(3^2)(5^1)(7^1) : 24 : max !!

660=(2^2)(3^1)(5^1)(11^1) : 24 : max !!

672=(2^5)(3^1)(7^1) : 24 : max !!

720=(2^4)(3^2)(5^1) : 30 : max !!

840=(2^3)(3^1)(5^1)(7^1) : 32 : max !!

1080=(2^3)(3^3)(5^1) : 32 : max !!

1260=(2^2)(3^2)(5^1)(7^1) : 36 : max !!

1440=(2^5)(3^2)(5^1) : 36 : max !!

1680=(2^4)(3^1)(5^1)(7^1) : 40 : max !!

2160=(2^4)(3^3)(5^1) : 40 : max !!

2520=(2^3)(3^2)(5^1)(7^1) : 48 : max !!

3360=(2^5)(3^1)(5^1)(7^1) : 48 : max !!

3780=(2^2)(3^3)(5^1)(7^1) : 48 : max !!

3960=(2^3)(3^2)(5^1)(11^1) : 48 : max !!

4200=(2^3)(3^1)(5^2)(7^1) : 48 : max !!

4320=(2^5)(3^3)(5^1) : 48 : max !!

4620=(2^2)(3^1)(5^1)(7^1)(11^1) : 48 : max !!

4680=(2^3)(3^2)(5^1)(13^1) : 48 : max !!

5040=(2^4)(3^2)(5^1)(7^1) : 60 : max !!

7560=(2^3)(3^3)(5^1)(7^1) : 64 : max !!

9240=(2^3)(3^1)(5^1)(7^1)(11^1) : 64 : max !!

10080=(2^5)(3^2)(5^1)(7^1) : 72 : max !!

12600=(2^3)(3^2)(5^2)(7^1) : 72 : max !!

13860=(2^2)(3^2)(5^1)(7^1)(11^1) : 72 : max !!

15120=(2^4)(3^3)(5^1)(7^1) : 80 : max !!

18480=(2^4)(3^1)(5^1)(7^1)(11^1) : 80 : max !!

20160=(2^6)(3^2)(5^1)(7^1) : 84 : max !!

25200=(2^4)(3^2)(5^2)(7^1) : 90 : max !!

27720=(2^3)(3^2)(5^1)(7^1)(11^1) : 96 : max !!

30240=(2^5)(3^3)(5^1)(7^1) : 96 : max !!

32760=(2^3)(3^2)(5^1)(7^1)(13^1) : 96 : max !!

36960=(2^5)(3^1)(5^1)(7^1)(11^1) : 96 : max !!

37800=(2^3)(3^3)(5^2)(7^1) : 96 : max !!

40320=(2^7)(3^2)(5^1)(7^1) : 96 : max !!

41580=(2^2)(3^3)(5^1)(7^1)(11^1) : 96 : max !!

42840=(2^3)(3^2)(5^1)(7^1)(17^1) : 96 : max !!

43680=(2^5)(3^1)(5^1)(7^1)(13^1) : 96 : max !!

45360=(2^4)(3^4)(5^1)(7^1) : 100 : max !!

50400=(2^5)(3^2)(5^2)(7^1) : 108 : max !!

55440=(2^4)(3^2)(5^1)(7^1)(11^1) : 120 : max !!

65520=(2^4)(3^2)(5^1)(7^1)(13^1) : 120 : max !!

75600=(2^4)(3^3)(5^2)(7^1) : 120 : max !!

83160=(2^3)(3^3)(5^1)(7^1)(11^1) : 128 : max !!

98280=(2^3)(3^3)(5^1)(7^1)(13^1) : 128 : max !!

110880=(2^5)(3^2)(5^1)(7^1)(11^1) : 144 : max !!

131040=(2^5)(3^2)(5^1)(7^1)(13^1) : 144 : max !!

138600=(2^3)(3^2)(5^2)(7^1)(11^1) : 144 : max !!

151200=(2^5)(3^3)(5^2)(7^1) : 144 : max !!

163800=(2^3)(3^2)(5^2)(7^1)(13^1) : 144 : max !!

166320=(2^4)(3^3)(5^1)(7^1)(11^1) : 160 : max !!

196560=(2^4)(3^3)(5^1)(7^1)(13^1) : 160 : max !!

221760=(2^6)(3^2)(5^1)(7^1)(11^1) : 168 : max !!

262080=(2^6)(3^2)(5^1)(7^1)(13^1) : 168 : max !!

277200=(2^4)(3^2)(5^2)(7^1)(11^1) : 180 : max !!

327600=(2^4)(3^2)(5^2)(7^1)(13^1) : 180 : max !!

332640=(2^5)(3^3)(5^1)(7^1)(11^1) : 192 : max !!

360360=(2^3)(3^2)(5^1)(7^1)(11^1)(13^1) : 192 : max !!

393120=(2^5)(3^3)(5^1)(7^1)(13^1) : 192 : max !!

415800=(2^3)(3^3)(5^2)(7^1)(11^1) : 192 : max !!

443520=(2^7)(3^2)(5^1)(7^1)(11^1) : 192 : max !!

471240=(2^3)(3^2)(5^1)(7^1)(11^1)(17^1) : 192 : max !!

480480=(2^5)(3^1)(5^1)(7^1)(11^1)(13^1) : 192 : max !!

491400=(2^3)(3^3)(5^2)(7^1)(13^1) : 192 : max !!

498960=(2^4)(3^4)(5^1)(7^1)(11^1) : 200 : max !!

554400=(2^5)(3^2)(5^2)(7^1)(11^1) : 216 : max !!

655200=(2^5)(3^2)(5^2)(7^1)(13^1) : 216 : max !!

665280=(2^6)(3^3)(5^1)(7^1)(11^1) : 224 : max !!

720720=(2^4)(3^2)(5^1)(7^1)(11^1)(13^1) : 240 : max !!

831600=(2^4)(3^3)(5^2)(7^1)(11^1) : 240 : max !!

942480=(2^4)(3^2)(5^1)(7^1)(11^1)(17^1) : 240 : max !!

982800=(2^4)(3^3)(5^2)(7^1)(13^1) : 240 : max !!

997920=(2^5)(3^4)(5^1)(7^1)(11^1) : 240 : max !!

1053360=(2^4)(3^2)(5^1)(7^1)(11^1)(19^1) : 240 : max !!

1081080=(2^3)(3^3)(5^1)(7^1)(11^1)(13^1) : 256 : max !!

1330560=(2^7)(3^3)(5^1)(7^1)(11^1) : 256 : max !!

1413720=(2^3)(3^3)(5^1)(7^1)(11^1)(17^1) : 256 : max !!

1441440=(2^5)(3^2)(5^1)(7^1)(11^1)(13^1) : 288 : max !!

1663200=(2^5)(3^3)(5^2)(7^1)(11^1) : 288 : max !!

現在のプログラムは、とりあえずある値を素因数分解して

その値の持つ約数の和を計算した後に、今までの約数の和と同じか以上の場合に

"max !!"という表示を付加する遅いプログラムのため、結構時間がかかっています。

（もっと高速なプログラムは考案中）

あまり、お仕事に差し支えないように　してください。

おかげで、物知りになりました。有り難うございます。

今後もよろしくお願いします。

問２で、集合の個数から、junko さんは求めておられますが、この計算をさらに、発展させていきます。
　ｎ（Ｕ）−ｎ（Ａ∪Ｂ）＝ｎ（Ｕ）−｛ｎ（Ａ）＋ｎ（Ｂ）−ｎ（Ａ∩Ｂ）｝
　＝３６−｛（３６÷２）＋（３６÷３）−（３６÷６）｝
　＝３６（１−１／２−１／３＋１／６）
　＝３６（１−１／２）（１−１／３）
　＝３６×１／２×２／３
　＝１２　・・・　（答）
さて、３６以下で３６との最大公約数が１である数とは、３６以下で３６と互いに素な数ということです。
　また、言葉を変えて言うと、２のい倍数でもなく３の倍数でもないという数のことです。
したがって、ｎ（Ａ∪Ｂ）の補集合となります。
　ここで、一般に、自然数Ｎについて、素因分解をします。
Ｎ＝ａ＾ｐ×ｂ＾ｑ×ｃ＾ｒ・・・・とします。
このＮ以下の自然数でＮと互いに素な数の個数はオイラー関数φ（Ｎ）といい、
φ（Ｎ）＝Ｎ（１−１／ａ）（１−１／ｂ）（１−１／ｃ）×・・・　と表すことができます。　＜終わり＞