約数

質問

自然数Ｎの約数の総和が60であるものをすべてもとめよ。

答えは(おそらく)24,38,59です。（しらみつぶしに探した結果）

どのように探したら効率いいでしょうか？

回答No.4

tom_onigiri · ベストアンサー

おそらくですが、#2さんと#3さんが言いたいのはこういうこと（↓）かな？

Nは５９以下で、Ｎ＝５９の時ＯＫなのは誰でも分かりますわな。
問題はそれ以外ですが、約数の総和の求め方を知っているのなら、
それと「ｍ＾０＋ｍ＾１＋…」を逆に利用する手があります。（ｍは素数）

６０＝２×３０＝３×２０＝４×１５＝５×１２＝６×１０ですが、
左と右の数（２と３０とか）がいずれも「ｍ＾０＋ｍ＾１＋…」で表せられるようになってないといけません。
(1)　２＝１＾０＋１＾１なのでｍ＝１となり、２×３０の場合は×。
(2)　３＝２＾０＋２＾１（１＋２）、２０＝１９＾０＋１９＾１（１＋１９）なので、２と１９に素因数分解される数となり、２×１９＝３８が解となります。
(3)　４＝３＾０＋３＾１（１＋３）、
１５＝２＾０＋２＾１＋２＾２＋２＾３（１＋２＋４＋８）なので、３×２×２×２＝２４が解となります。
(4) ５＝４＾０＋４＾１（１＋４）でｍ＝４となり、これは素数でないので５×１２の場合は×。
(5) １０＝９＾０＋９＾１（１＋９）でこの時ｍ＝９となり、これは素数でないので６×１０は×。
結果、答えは小さいほうから２４、３８、５９（素数なのでＯＫ）となります。

しらみつぶしって感じもしますけど、わかりました？

お礼

はあ、なるほど、そういうことですか。
どもです、

回答No.3

yuusukekyouju

>答えは(おそらく)24,38,59です。

たしかにそうなります。
NO2の方のヒントを具体的に
24＝2＾3×3
約数の総和
（1+2+2＾2+2＾3）×（1+3）＝60

38＝2×19
約数の総和
（1+2）×（1+19）＝60

ヒントになりましたか。

補足

いや、素因数をどうやって決定するんですか？

ある整数の約数の総和の求め方は知っています。
そこがわからないんじゃないです。

回答No.2

kokusuda

宿題かもしれないので（笑）
そのものズバリは避けた方が良いのかな？

自然数の約数の総和は計算式で求められます。
この計算式から逆に自然数を計算できます。
ヒントは素因数分解と素数の関係です。
行列式でも求められますが、
６０程度だったら普通に計算したほうが
効率的と思います。

参考URL：

http://www.ansas.org/sanzyutsuman/Pages/unit2.html

補足

宿題ではないんですが。
えー？Ｎじゃ素因数分解できませんよ？

＞普通に計算
とはいかなるものでしょか？
＞行列式でも求められます
こちらに興味津々。

回答No.1

massie

(1)、５９以外の素数はだめ。１、２、３、５、７、
　11、13、17、19、23、29、31、37、41、43、47、
　53、
(2)、４０以上の偶数は20以上の約数を持つのでだめ。
　40、42、44、46、48、50、52、54、56、58、60
(3)、45以上の3の倍数もダメ
　45、51、57
(4)、16以下の数はだめ。１～８の総和と16をたしても　60にならない
　４、６、８、９、１０、１２、１４、１６

　だいぶ絞れたけどこんなことやっている間に、しらみつぶしにやった方が早いですね。

お礼

どうもです。