PythonとRustで！友愛数の組を見つけてみよう!

PythonやRustで数学的な問題を解いてみたい方へ――
前回の記事「友愛数入門! 数の面白シリーズ!」では、友愛数について紹介しました。

今回はその友愛数を、定義に基づいてPythonとRustで実際にプログラムを組んで探索していきます。

Pythonでの基礎的な実装から始め、Rustを使った高速化にも挑戦。
初心者でも理解しやすいコードで、数論の面白さと言語間の違いを体験できます。

「プログラミングで数学を楽しむ」シリーズ第2弾、どうぞお楽しみください！

Contents

友愛数とは（復習）
Pythonで友愛数を探す：実装＆解説
Rustで友愛数探索を高速化してみよう！
パフォーマンス比較 (Python vs Rust)
まとめと次回予告：サービト・イブン＝クッラの方法へ

友愛数とは（復習）

友愛数

２つの自然数 $a$ と $b$ が友愛数であるとは、次の条件を満たす時である。

$\sigma(a) – a = b$ かつ $\sigma(b) – b = a$

ここで、 $\sigma(n)$ は $n$ の正の約数の総和である。

以下は友愛数の組の例になります。

$(220,284)$
$(1184, 1210)$
$(2620, 2924)$
$(5020, 5564)$
$(6232, 6368)$

Pythonで友愛数を探す：実装＆解説

pythonで1から10000までの友愛数を列挙します。
ソースコードは以下になります。

import time

def sum_of_proper_divisors(n):
    """nの真の約数の和を返す（1からn-1の約数の和）"""
    total = 0
    for i in range(1, n):  # 1からn-1までの整数について調べる
        if n % i == 0:  # iがnの約数であれば 
            total += i  # 合計に加える
    return total


def find_amicable_pairs(limit):
    """指定された範囲で友愛数のペアを探す"""
    pairs = []  # 友愛数の組を格納するリストを初期化
    for a in range(2, limit):  # 2から指定された最大値まで調べる
        b = sum_of_proper_divisors(a) # 真の約数の和を計算する
        #  b>aを条件にすることで、(b,a)のような重複ペアを除く
        if b > a and sum_of_proper_divisors(b) == a: # b > aでbの真の約数の和がaなら友愛数  
            pairs.append((a, b)) # 友愛数の組のリストに追加
    return pairs


if __name__ == '__main__':
    start = time.time()
    # 10000未満の友愛数ペアを探索する
    amicable_pairs = find_amicable_pairs(10000)
    print("10000未満の友愛数のペア:")
    for a, b in amicable_pairs:
        print(f"{a} と {b}")
    end = time.time()
    print(f"処理時間: {end - start:.5f}秒")

結果は以下になります。

10000未満の友愛数のペア:
220 と 284
1184 と 1210
2620 と 2924
5020 と 5564
6232 と 6368
処理時間: 2.26706秒

ソースコードについて、解説します。

sum_of_proper_divisors関数は引数nの真の約数 (自分自身を除いた約数)の和を計算して返却しています。
find_amicable_pairs関数は引数limitの数までの友愛数の組をリストに追加して、そのリストを返しています。

ポイントになるのは次の手順の部分になります。

2からlimit-1までの数aの真の約数の和を計算してbという変数に格納
逆にbの真の約数の和を計算し、aと等しいかをチェック
aと等しければ、組(a,b)は友愛数の組になる
ただし、組 (b,a)も友愛数の組になり、重複してしまうので片方を除外したい。
そのため、b > aの場合のみ友愛数の組のリストに加える

Rustで友愛数探索を高速化してみよう！

Rustでも同様に友愛数の組を探すプログラムを組んでみます。

use std::time::Instant; // 時間計測のためのモジュールをインポート

/// n の真の約数の合計を返す関数（1 から n-1 までの範囲）
fn sum_of_proper_divisors(n: u64) -> u64 {
    let mut total: u64 = 0;
    for i in 1..n {
        if n % i == 0 {
            total += i;
        }
    }
    total
}

/// 与えられた上限までの友愛数のペアを探す関数
fn find_amicable_pairs(limit: u64) -> Vec<(u64, u64)> {
    let mut pairs = Vec::new();

    for a in 2..limit {
        let b = sum_of_proper_divisors(a);
        if b > a && sum_of_proper_divisors(b) == a {
            pairs.push((a, b));
        }
    }

    pairs
}

fn main() {
    // 開始時間の記録
    let start = Instant::now();
    let limit: u64 = 10000;
    let amicable_pairs = find_amicable_pairs(limit);
    println!("{} 未満の友愛数のペア:", limit);
    for (a, b) in amicable_pairs {
        println!("{} と {}", a, b);
    }
    // 経過時間を計算
    let duration = start.elapsed();
    println!("かかった時間: {:.6}秒", duration.as_secs_f64());
}

結果は以下になります。

10000 未満の友愛数のペア:
220 と 284  
1184 と 1210
2620 と 2924
5020 と 5564
6232 と 6368
かかった時間: 0.346076秒

プログラムの内容はPythonと同じです。
完全数の時の探索と同様に、Rustの方が処理速度は速いですね！

パフォーマンス比較 (Python vs Rust)

ここでは、find_amicable_parisに渡す引数limitの値を10000,20000,50000,100000と変えて、Python版とRust版で処理時間を比較してみます。

limit	Python (秒)	Rust (秒)
10000	2.3	0.34
20000	9.1	1.4
50000	57.4	8.6
100000	228.6	34.2

※測定環境は、AMD Ryzen 7 3700X 8-Core Processor, Windows 10 Home Version 2009になります。

Rustの実行時間は、Pythonに比べて圧倒的に短く、特に入力が大きくなるほどその差は顕著になります。
Pythonは直感的で書きやすい反面、速度が求められる場面ではRustのような低レベル言語が強みを発揮します。