約数和は収束するのか

任意自然数の約数和を延々と計算しつづけると一体どうなるかという実験(途中で逸れる)

概要

2005/05/21

メルセンヌ素数・完全数を書いてて気づいた。 完全数の場合約数和は常に自身だが、不足数・過剰数の約数和の約数和をどんどん求めつづけていくと一体どうなるのだろうか? 全体的に見て不足数が圧倒的であるし、素数の約数和は1に収束することから最後は1に収束するのか?というわけで実験してみた。 (完全数と5000万を越える数は自動的に除外します)

任意数を指定し実行

2005/05/21

任意指定は範囲自由だが、ランダムを押すと1〜50000の範囲から無造作に選んだ数値を使う。範囲内の数値を根こそぎにするプログラムを作ってみた。(完全数と1000万以上は除外)。が・・・220のとき約数和が284とで無限に繰り返された。220を入れてみると分かるが無限に続く。

よくよく考えれば友愛数というものが存在していた。これでは収束も発散もしない。ただの無限ループだ。というわけで急遽プログラムを変更し、任意範囲で友愛数を検索してみる事にした。

友愛数検索デモ

2005/05/21

20000以下を根こそぎ検索したところ

220 & 284
1184 & 1210
2620 & 2924
5020 & 5564
6232 & 6368
10744 & 10856
12285 & 14595
17296 & 18416

9組の友愛数を得ることができた。220 & 284の発見者はピタゴラス。285〜10000では1184& 1210を除き全てオイラーによるもの。1184と1210は数学史上の謎らしいが、今となってはこんなバカでも求められる時代になった。

友愛数のほかに社交数なるものもある。これは3つ以上の自然数の約数和がループするもの。12496,14288,15472,14536,14264が社交数の一つ。ちなみに3つ以上と言ったが肝心の3つの社交数は見つかっていない。社交数を求めるプログラムは面倒なので作らないが暇な人は作って試してください(無責任

結局、最初に挙げた題から大きくそれた罠。

友愛数検索デモ-高速化

2005/09/23

初期のデモでは、任意の数に対し約数と思われる数を総当りで割り算していたが、これだと数値が上がると計算量が急激に増加する。そこで、一度素因数分解し素因数から約数を生成するタイプのアルゴリズムを考案。この場合幾ら数が多くても素因数分解時に捜索する因数は√Nで効率がいい。しかし因数が多すぎる場合、例えば10個の因数を持つ数と13個の因数を持つ数の約数生成パターンは、10個--3628800パターンに対し13個--6227020800パターンと急激に増加する。こんなことをやるなら旧式の総当りのほうが遥かに高速。このデモでは、因数が一定数を超えるとアルゴリズムを旧式に変更するダブルエンジン方式を採用している。アルゴリズム切り替えによって計算効率が50%アップ。さらに、奇数の場合友愛数は3で割り切れるという予想を組み込みさらに数%効率アップ。初期のデモでは1〜20000までの検索が限界だったが、これは1〜100000までの範囲を350秒(MSIE6)で検索できる。以下に計算結果を載せておく。

====友愛数検索====
範囲:2~100000
個数:13組
Cost:336.047s

220&284
1184&1210
2620&2924
5020&5564
6232&6368
10744&10856
12285&14595
17296&18416
63020&76084
66928&66992
67095&71145
69615&87633
79750&88730
====友愛数検索====
範囲:100001~150000
個数:5組
Cost:302.75s

100485&124155
122265&139815
122368&123152
141664&153176
142310&168730

ページ情報

作成日時
2005/05/21
最終更新日時
2005/09/23
HTML4.01版
index.html
XHTML1.1版
index.xhtml
XML原本
index.xml