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