[Rust] シェルピンスキー数の検証

はじめに

Rustの勉強を兼ねて、指定された数値がシェルピンスキー数かどうかをチェック（探索？）するプログラムを作成しました。非実用的なものですが。

シェルピンスキー数とは？

シェルピンスキー数とは $S_n = k \cdot 2^n + 1$ が任意の正の整数 $n$ に対して合成数（素数でない）となるような奇数 $k$ のことです。

ポーランドの数学者であるシェルピンスキー（あるいはシェルピニスキ）さんといえば、フラクタル図形のシェルピンスキーのギャスケットや、シェルピンスキーのカーペット、あるいはシェルピンスキー曲線などが有名な感じですが。

Qiita にも「シェルピンスキー数」の紹介記事がありました🐸。

正確には「第二種シェルピンスキー数」というようですね。本記事では単に「シェルピンスキー数」と呼ばせていただきます。

既知の最小のシェルピンスキー数は $k=78\thinspace557$ であり、以下のように場合分けをして証明されています（$m$ は自然数）。

• $n = 2 m + 0$ の時、$S_n$ は $3$ で割り切れる
• $n = 4 m + 1$ の時、$S_n$ は $5$ で割り切れる
• $n = 12 m + 7$ の時、$S_n$ は $7$ で割り切れる
• $n = 12 m + 11$ の時、$S_n$ は $13$ で割り切れる
• $n = 36 m + 3$ の時、$S_n$ は $73$ で割り切れる
• $n = 36 m + 15$ の時、$S_n$ は $19$ で割り切れる
• $n = 36 m + 27$ の時、$S_n$ は $37$ で割り切れる

この説明では、例えば２番目で「$n = 4 m + 1$ の時、$S_n$ は $5$ で割り切れる」としていますが、これを詳細に書くとまず $2^4 \equiv 1 \pmod 5$ であるので

\begin{align}
S_n &= 78\thinspace557 \cdot 2^n + 1 \\
    &= 78\thinspace557 \cdot 2^{4 m + 1} + 1 \\
    &= 78\thinspace557 {(2^4)}^m \cdot 2^1 + 1 \\
    &\equiv 78\thinspace557 {(1)}^m \cdot 2 + 1 \pmod 5 \\
    &\equiv 157\thinspace114 + 1 \pmod 5 \\
    &\equiv 0 \pmod 5 \\
\end{align}

となり、すべての $m$ に対して $5$ で割り切れることがわかります。ほかのケースもほぼ同様です。また、分割数が徐々に大きくなっていますが、ちゃんと考えると全部のパターンを網羅していることがわかると思います。

探索アルゴリズム

これと同じ方式で機械的にシェルピンスキー数を求めるため、以下のようなアルゴリズムを採用しています。

元の式に $ n = a m + b$ （ただし $a$ は正整数、$b$ は $0 \leq b < a$ の範囲の整数）を代入して式を変形します。

\begin{align}
S_n &= k \cdot 2^n + 1 \\
    &= k \cdot 2^{a \cdot m + b} + 1 \\
    &= k \cdot {(2^a)}^m \cdot 2^b + 1
\end{align}

この式において、とある分割数 $a$ のときに、$b$ が $0,1,2,\dots ,a-1$ のすべてに対して、次の条件を満たす素数 $p$ がそれぞれ存在すれば、$S_n$ はすべて合成数であると判定できます（各 $b$ ごとにこの条件を満たす素数が存在すればよい。同じ素数である必要はない）。

• 条件 1： $2^a \equiv 1 \pmod p$
• 条件 2： $k \cdot 2^b + 1 \equiv 0 \pmod p$

念のため簡単に説明すれば、【条件 1】を満たせば、$m$ がいくつであっても $(2^a)^m \equiv 1^m \equiv 1 \pmod p$ となるため、残りは $k \cdot 1 \cdot 2^b + 1 \equiv k \cdot 2^b + 1 \equiv 0 \pmod p$ となり、これが【条件 2】になります。

このような素数 $p$ をそれぞれの $b$ に対してみつけられれば、 $k \cdot 2^n + 1$ はすべての $n$ に対して少なくとも一つの素因数を持つため、$k$ はシェルピンスキー数であると判定できます。

なお、チェックする $p$ は素数に限定して問題ありません。なぜなら、ある合成数 $q$ が $S_n$ を割り切るとしても、その $q$ は必ず素数である素因数 $p$ を持ち、その素数 $p$ も同様に $S_n$ を割り切りますし、そして合成数 $q$ よりも素因数である素数 $p$ の方が小さいからです。

一方で、シェルピンスキー数と親和性の高そうな フェルマーの小定理 に関しては、実際に試してみると必ずしも $a$ が素数から 1 引いた値であるとは限らないので、プログラムの力押しで検索する場合には利用しないことにしました。

また実装する際の性能的には、各 b に対して素数リストを【条件 1】と【条件 2】でチェックするよりも、まずは【条件 1】で素数リストを絞り込んでから、各 b に対して絞り込んだ素数群で【条件 2】のチェックをする方が速く判定できるようです（探索上限をあげると、体感できる程度には性能が変わる）。

場合分けした場合の割り切れる素数を探索

fn find_covering_primes(k: usize, a: usize, primes: &[usize]) -> Vec<Option<usize>> {
    use modpow::Modpow;

    // 条件1: 2^a mod p == 1
    let filtered_primes: Vec<usize> = primes
        .iter()
        .copied()
        .filter(|&p| 2.modpow(a, p) == 1)
        .collect();

    // 条件2: k*(2^b)+1 mod p == 0
    (0..a)
        .map(|b| {
            filtered_primes
                .iter()
                .find(|&&p| (k * 2.modpow(b, p) + 1) % p == 0)
                .cloned()
        })
        .collect()
}

ちなみに、Rust の BigUint などには modpow がありますが、usize などには（有名なクレートが）なさそうなので、勉強を兼ねて繰り返し二乗法（ Modular exponentiation ）で計算する modpow を自作してみました（つまり標準機能では 2.modpow(x, y) とはできないので注意。今回は usize でだけ計算できればよいですが、お勉強のためにトレイト（トレイト境界）を使ってみた。以下はロジック部のみ）。

modpowの計算のロジック部（抜粋）

    fn modpow(self, mut exp: Self, modu: Self) -> Self {
        let zero: Self = 0u8.into();
        let one: Self = 1u8.into();
        let two: Self = 2u8.into();

        if modu == zero {
            panic!("modulus must be non-zero");
        }
        if modu == one {
            return zero;
        }
        let mut result = one;
        let mut base = self % modu;
        while exp != zero {
            if exp % two == one {
                result = (result * base) % modu;
            }
            exp >>= 1u8;
            base = (base * base) % modu;
        }
        result
    }

探索方向は分割数 $a$ を大きくする方向と、素数 $p$ の上限を大きくする方向の2つがありますが、実装の都合上素数は事前に エラトステネスの篩 で生成しておき、分割数 $a$ を大きくする方向で探索を行います。

エラトステネスの篩

pub fn eratosthenes<T: From<usize>>(limit: usize) -> Vec<T> {
    if limit < 2 {
        return vec![];
    }
    let mut is_prime = vec![true; limit + 1];
    is_prime[0] = false;
    is_prime[1] = false;
    for i in 2..=limit.isqrt() {
        if is_prime[i] {
            for j in (i * i..=limit).step_by(i) {
                is_prime[j] = false;
            }
        }
    }
    is_prime
        .iter()
        .enumerate()
        .filter(|&(_, &prime)| prime)
        .map(|(i, _)| T::from(i))
        .collect()
}

人が行う証明は分割数が少ないものから枝刈りするような感じでしたが、機械的に処理する（というか実装に手を抜く）都合上、枝刈りしないで分割数のまま力押しで検証しています。全部の状態を出力すると出すぎるので割り切れるカバー率が上昇した場合のみ状況を出力するようにしました。実際の出力イメージは下の方の実行例の１件目を見てください。

分割数aを増やしながらシェルピンスキー数であるかを判定

fn search_sierpinski_number(k: usize, max_a: usize, primes: &[usize]) {
    let mut best_rate = 0.0;
    for a in 2..=max_a {
        let covering_primes = find_covering_primes(k, a, primes);
        let missing_count = covering_primes.iter().filter(|p| p.is_none()).count();
        let coverage_rate = (a - missing_count) as f64 / a as f64;

        if best_rate < coverage_rate {
            best_rate = coverage_rate;
            for (b, covering_prime) in covering_primes.iter().enumerate() {
                if let Some(p) = covering_prime {
                    println!("{}*2^({}m+{})+1 mod {} = 0", k, a, b, p);
                } else {
                    println!("{}*2^({}m+{})+1 (prime not found)", k, a, b);
                }
            }
            println!("-- {}/{} = {}%", a - missing_count, a, best_rate * 100.0);
            println!();
        }
        if missing_count == 0 {
            break;
        }
    }
}

実際のソースコードは以下のリポジトリにあります。

実行方法

cargo run --release -- --max-a MAX_A --max-prime MAX_PRIME K

あるいはビルド後に

./target/release/sierpinski-number-rs --max-a MAX_A --max-prime MAX_PRIME K

• K: シェルピンスキー数の基数(省略時は 78557)
• MAX_A: 探索する a の最大値(省略時は 1024)
• MAX_PRIME: チェックする素数pの上限(省略時は 20000)

実行例

k=78557 の場合

既知の最小のシェルピンスキー数である $k=78\thinspace557$ を与えた場合、以下のような出力が得られます。

$ cargo run --release -- 78557
78557*2^(2m+0)+1 mod 3 = 0
78557*2^(2m+1)+1 (prime not found)
-- 1/2 = 50%

78557*2^(4m+0)+1 mod 3 = 0
78557*2^(4m+1)+1 mod 5 = 0
78557*2^(4m+2)+1 mod 3 = 0
78557*2^(4m+3)+1 (prime not found)
-- 3/4 = 75%

78557*2^(12m+0)+1 mod 3 = 0
78557*2^(12m+1)+1 mod 5 = 0
78557*2^(12m+2)+1 mod 3 = 0
78557*2^(12m+3)+1 (prime not found)
78557*2^(12m+4)+1 mod 3 = 0
78557*2^(12m+5)+1 mod 5 = 0
78557*2^(12m+6)+1 mod 3 = 0
78557*2^(12m+7)+1 mod 7 = 0
78557*2^(12m+8)+1 mod 3 = 0
78557*2^(12m+9)+1 mod 5 = 0
78557*2^(12m+10)+1 mod 3 = 0
78557*2^(12m+11)+1 mod 13 = 0
-- 11/12 = 91.66666666666666%

78557*2^(36m+0)+1 mod 3 = 0
78557*2^(36m+1)+1 mod 5 = 0
78557*2^(36m+2)+1 mod 3 = 0
78557*2^(36m+3)+1 mod 73 = 0
78557*2^(36m+4)+1 mod 3 = 0
78557*2^(36m+5)+1 mod 5 = 0
78557*2^(36m+6)+1 mod 3 = 0
78557*2^(36m+7)+1 mod 7 = 0
78557*2^(36m+8)+1 mod 3 = 0
78557*2^(36m+9)+1 mod 5 = 0
78557*2^(36m+10)+1 mod 3 = 0
78557*2^(36m+11)+1 mod 13 = 0
78557*2^(36m+12)+1 mod 3 = 0
78557*2^(36m+13)+1 mod 5 = 0
78557*2^(36m+14)+1 mod 3 = 0
78557*2^(36m+15)+1 mod 19 = 0
78557*2^(36m+16)+1 mod 3 = 0
78557*2^(36m+17)+1 mod 5 = 0
78557*2^(36m+18)+1 mod 3 = 0
78557*2^(36m+19)+1 mod 7 = 0
78557*2^(36m+20)+1 mod 3 = 0
78557*2^(36m+21)+1 mod 5 = 0
78557*2^(36m+22)+1 mod 3 = 0
78557*2^(36m+23)+1 mod 13 = 0
78557*2^(36m+24)+1 mod 3 = 0
78557*2^(36m+25)+1 mod 5 = 0
78557*2^(36m+26)+1 mod 3 = 0
78557*2^(36m+27)+1 mod 37 = 0
78557*2^(36m+28)+1 mod 3 = 0
78557*2^(36m+29)+1 mod 5 = 0
78557*2^(36m+30)+1 mod 3 = 0
78557*2^(36m+31)+1 mod 7 = 0
78557*2^(36m+32)+1 mod 3 = 0
78557*2^(36m+33)+1 mod 5 = 0
78557*2^(36m+34)+1 mod 3 = 0
78557*2^(36m+35)+1 mod 13 = 0
-- 36/36 = 100%

k=21181 の場合

巨大数研究 Wikiの『第2種シェルピンスキー数』から、反例素数が見つかっていないシェルピンスキー数候補のなかで、最小の $k=21\thinspace181$ の場合を以下に示します。

全部を出すと長いので、カバー率のみです。分割数を最大 10 000 まで見ています。

$ ./target/release/sierpinski-number-rs -max-a 10000 21181 | grep '^--'
-- 1/2 = 50%
-- 3/4 = 75%
-- 7/8 = 87.5%
-- 11/12 = 91.66666666666666%
-- 23/24 = 95.83333333333334%
-- 116/120 = 96.66666666666667%
-- 256/264 = 96.96969696969697%
-- 1288/1320 = 97.57575757575758%
-- 9024/9240 = 97.66233766233766%

結果は整理すると以下のようになりました（コマンドの出力は整理されていませんが、さすがに長くなるので手動で整理しました）。

• $n = 2 m + 1$ の時、$S_n$ は $3$ で割り切りれる
• $n = 4 m + 2$ の時、$S_n$ は $5$ で割り切りれる
• $n = 8 m + 0$ の時、$S_n$ は $17$ で割り切りれる
• $n = 12 m + 0$ の時、$S_n$ は $7$ で割り切りれる
• $n = 12 m + 4$ の時、$S_n$ は $13$ で割り切りれる
• $n = 24 m + 20$ の時、$S_n$ を割り切る素数は見つからなかった

実際には120分割以上すればもう少しだけは見つかります。

もし $k=21\thinspace181$ の場合の反例素数があるとすれば $21\thinspace181 \cdot 2^{24 m + 20} + 1$ という形でしか存在し得ないことがわかります。

k=22699 の場合

その他のシェルピンスキー数候補も結果を表示します（対象の候補は手打ちなので、打ち間違いもあるかも）。

$ ./target/release/sierpinski-number-rs --max-a 10000 22699 | grep '^--'
-- 1/2 = 50%
-- 3/4 = 75%
-- 7/8 = 87.5%
-- 11/12 = 91.66666666666666%
-- 23/24 = 95.83333333333334%
-- 35/36 = 97.22222222222221%
-- 71/72 = 98.61111111111111%
-- 356/360 = 98.88888888888889%
-- 3920/3960 = 98.98989898989899%

• $n = 2 m + 1$ の時、$S_n$ は $3$ で割り切りれる
• $n = 4 m + 0$ の時、$S_n$ は $5$ で割り切りれる
• $n = 8 m + 2$ の時、$S_n$ は $17$ で割り切りれる
• $n = 12 m + 2$ の時、$S_n$ は $7$ で割り切りれる
• $n = 12 m + 6$ の時、$S_n$ は $13$ で割り切りれる
• $n = 36 m + 22$ の時、$S_n$ は $19$ で割り切りれる
• $n = 36 m + 34$ の時、$S_n$ は $73$ で割り切りれる
• $n = 72 m + 46$ の時、$S_n$ を割り切る素数は見つからなかった

k=24737 の場合

$ ./target/release/sierpinski-number-rs --max-a 10000 24737 | grep '^--'
-- 1/2 = 50%
-- 3/4 = 75%
-- 7/8 = 87.5%
-- 11/12 = 91.66666666666666%
-- 23/24 = 95.83333333333334%
-- 117/120 = 97.5%
-- 1054/1080 = 97.5925925925926%
-- 1523/1560 = 97.62820512820512%
-- 4338/4440 = 97.70270270270271%

• $n = 2 m + 0$ の時、$S_n$ は $3$ で割り切りれる
• $n = 4 m + 1$ の時、$S_n$ は $5$ で割り切りれる
• $n = 8 m + 3$ の時、$S_n$ は $17$ で割り切りれる
• $n = 12 m + 3$ の時、$S_n$ は $7$ で割り切りれる
• $n = 12 m + 11$ の時、$S_n$ は $13$ で割り切りれる
• $n = 24 m + 7$ の時、$S_n$ を割り切る素数は見つからなかった

k=55459 の場合

$ ./target/release/sierpinski-number-rs --max-a 10000 55459 | grep '^--'
-- 1/2 = 50%
-- 3/4 = 75%
-- 11/12 = 91.66666666666666%
-- 34/36 = 94.44444444444444%
-- 173/180 = 96.11111111111111%
-- 1219/1260 = 96.74603174603175%
-- 8537/8820 = 96.79138321995465%

• $n = 2 m + 1$ の時、$S_n$ は $3$ で割り切りれる
• $n = 4 m + 0$ の時、$S_n$ は $5$ で割り切りれる
• $n = 12 m + 2$ の時、$S_n$ は $7$ で割り切りれる
• $n = 12 m + 6$ の時、$S_n$ は $13$ で割り切りれる
• $n = 36 m + 34$ の時、$S_n$ は $37$ で割り切りれる
• $n = 36 m + 10$ の時、$S_n$ を割り切る素数は見つからなかった
• $n = 36 m + 22$ の時、$S_n$ を割り切る素数は見つからなかった

k=67607 の場合

$ ./target/release/sierpinski-number-rs --max-a 10000 67607 | grep '^--'
-- 1/2 = 50%
-- 3/4 = 75%
-- 7/8 = 87.5%
-- 18/20 = 90%
-- 22/24 = 91.66666666666666%
-- 38/40 = 95%
-- 69/72 = 95.83333333333334%
-- 117/120 = 97.5%
-- 176/180 = 97.77777777777777%
-- 356/360 = 98.88888888888889%
-- 2500/2520 = 99.20634920634922%

• $n = 2 m + 0$ の時、$S_n$ は $3$ で割り切りれる
• $n = 4 m + 1$ の時、$S_n$ は $5$ で割り切りれる
• $n = 8 m + 7$ の時、$S_n$ は $17$ で割り切りれる
• $n = 8 m + 3$ の時、$S_n$ を割り切る素数は見つからなかった

10 000 分割までで 99.2% は、今回チェックしたシェルピンスキー数候補の中では一番カバー率の高いものでした。
その割には、分割数が 8 分割 ⇒ 20 分割 ⇒ 24 分割 ⇒ 40 分割みたいになっているので、結果の整理を途中で打ち切ってしまいました。

k=79309 の場合

$ ./target/release/sierpinski-number-rs --max-a 10000 79309 | grep '^--'
-- 1/2 = 50%
-- 3/4 = 75%
-- 7/8 = 87.5%
-- 11/12 = 91.66666666666666%
-- 23/24 = 95.83333333333334%
-- 35/36 = 97.22222222222221%
-- 71/72 = 98.61111111111111%
-- 356/360 = 98.88888888888889%
-- 1781/1800 = 98.94444444444444%
-- 2496/2520 = 99.04761904761905%
-- 3924/3960 = 99.0909090909091%

• $n = 2 m + 1$ の時、$S_n$ は $3$ で割り切りれる
• $n = 4 m + 0$ の時、$S_n$ は $5$ で割り切りれる
• $n = 8 m + 2$ の時、$S_n$ は $17$ で割り切りれる
• $n = 12 m + 6$ の時、$S_n$ は $7$ で割り切りれる
• $n = 12 m + 10$ の時、$S_n$ は $13$ で割り切りれる
• $n = 36 m + 14$ の時、$S_n$ は $19$ で割り切りれる
• $n = 36 m + 26$ の時、$S_n$ は $109$ で割り切りれる
• $n = 72 m + 38$ の時、$S_n$ を割り切る素数は見つからなかった

k=79817 の場合

$ ./target/release/sierpinski-number-rs --max-a 10000 79817 | grep '^--'
-- 1/2 = 50%
-- 3/4 = 75%
-- 7/8 = 87.5%
-- 22/24 = 91.66666666666666%
-- 37/40 = 92.5%
-- 68/72 = 94.44444444444444%
-- 114/120 = 95%
-- 348/360 = 96.66666666666667%
-- 1046/1080 = 96.85185185185186%
-- 1744/1800 = 96.88888888888889%
-- 2448/2520 = 97.14285714285714%
-- 7356/7560 = 97.3015873015873%

• $n = 2 m + 0$ の時、$S_n$ は $3$ で割り切りれる
• $n = 4 m + 1$ の時、$S_n$ は $5$ で割り切りれる
• $n = 8 m + 3$ の時、$S_n$ は $17$ で割り切りれる
• $n = 24 m + 7$ の時、$S_n$ は $7$ で割り切りれる
• $n = 24 m + 15$ の時、$S_n$ を割り切る素数は見つからなかった
• $n = 24 m + 23$ の時、$S_n$ を割り切る素数は見つからなかった

k=91459 の場合

$ ./target/release/sierpinski-number-rs --max-a 10000 91459 | grep '^--'
-- 1/2 = 50%
-- 3/4 = 75%
-- 28/36 = 77.77777777777779%
-- 142/180 = 78.88888888888889%
-- 316/396 = 79.7979797979798%
-- 949/1188 = 79.8821548821549%
-- 1600/1980 = 80.8080808080808%
-- 4805/5940 = 80.89225589225589%
-- 8081/9900 = 81.62626262626263%

• $n = 2 m + 1$ の時、$S_n$ は $3$ で割り切りれる
• $n = 4 m + 0$ の時、$S_n$ は $5$ で割り切りれる
• $n = 36 m + 30$ の時、$S_n$ は $19$ で割り切りれる
• $n = 36 m + 2$ の時、$S_n$ を割り切る素数は見つからなかった
• $n = 36 m + 6$ の時、$S_n$ を割り切る素数は見つからなかった
• $n = 36 m + 10$ の時、$S_n$ を割り切る素数は見つからなかった
• $n = 36 m + 14$ の時、$S_n$ を割り切る素数は見つからなかった
• $n = 36 m + 18$ の時、$S_n$ を割り切る素数は見つからなかった
• $n = 36 m + 22$ の時、$S_n$ を割り切る素数は見つからなかった
• $n = 36 m + 26$ の時、$S_n$ を割り切る素数は見つからなかった
• $n = 36 m + 34$ の時、$S_n$ を割り切る素数は見つからなかった

今回チェックしたシェルピンスキー数候補の中では、一番カバー率が低かったもの。9900 分割してようやく 81 % でした（ほかは大体 95% 以上になっている）。

k=131179 の場合

$ ./target/release/sierpinski-number-rs --max-a 10000 131179 | grep '^--'
-- 1/2 = 50%
-- 3/4 = 75%
-- 11/12 = 91.66666666666666%
-- 35/36 = 97.22222222222221%
-- 386/396 = 97.47474747474747%
-- 1931/1980 = 97.52525252525253%
-- 2636/2700 = 97.62962962962963%
-- 5803/5940 = 97.6936026936027%
-- 9675/9900 = 97.72727272727273%

• $n = 2 m + 1$ の時、$S_n$ は $3$ で割り切りれる
• $n = 4 m + 0$ の時、$S_n$ は $5$ で割り切りれる
• $n = 12 m + 6$ の時、$S_n$ は $7$ で割り切りれる
• $n = 12 m + 10$ の時、$S_n$ は $13$ で割り切りれる
• $n = 36 m + 14$ の時、$S_n$ は $19$ で割り切りれる
• $n = 36 m + 26$ の時、$S_n$ は $73$ で割り切りれる
• $n = 36 m + 2$ の時、$S_n$ を割り切る素数は見つからなかった

k=152267 の場合

$ ./target/release/sierpinski-number-rs --max-a 10000 152267 | grep '^--'
-- 1/2 = 50%
-- 3/4 = 75%
-- 7/8 = 87.5%
-- 11/12 = 91.66666666666666%
-- 23/24 = 95.83333333333334%
-- 70/72 = 97.22222222222221%
-- 117/120 = 97.5%
-- 354/360 = 98.33333333333333%
-- 1064/1080 = 98.51851851851852%
-- 2484/2520 = 98.57142857142858%
-- 3195/3240 = 98.61111111111111%
-- 7464/7560 = 98.73015873015873%

• $n = 2 m + 0$ の時、$S_n$ は $3$ で割り切りれる
• $n = 4 m + 1$ の時、$S_n$ は $5$ で割り切りれる
• $n = 8 m + 7$ の時、$S_n$ は $17$ で割り切りれる
• $n = 12 m + 7$ の時、$S_n$ は $7$ で割り切りれる
• $n = 12 m + 11$ の時、$S_n$ は $13$ で割り切りれる
• $n = 24 m + 15$ の時、$S_n$ は $17$ で割り切りれる
• $n = 72 m + 27$ の時、$S_n$ は $19$ で割り切りれる
• $n = 72 m + 3$ の時、$S_n$ を割り切る素数は見つからなかった
• $n = 72 m + 51$ の時、$S_n$ を割り切る素数は見つからなかった

k=156511 の場合

$ ./target/release/sierpinski-number-rs --max-a 10000 156511 | grep '^--'
-- 1/2 = 50%
-- 3/4 = 75%
-- 11/12 = 91.66666666666666%
-- 35/36 = 97.22222222222221%
-- 71/72 = 98.61111111111111%
-- 356/360 = 98.88888888888889%
-- 1781/1800 = 98.94444444444444%
-- 3208/3240 = 99.01234567901234%
-- 3924/3960 = 99.0909090909091%

• $n = 2 m + 1$ の時、$S_n$ は $3$ で割り切りれる
• $n = 4 m + 2$ の時、$S_n$ は $5$ で割り切りれる
• $n = 12 m + 4$ の時、$S_n$ は $13$ で割り切りれる
• $n = 12 m + 8$ の時、$S_n$ は $7$ で割り切りれる
• $n = 36 m + 0$ の時、$S_n$ は $73$ で割り切りれる
• $n = 36 m + 24$ の時、$S_n$ は $19$ で割り切りれる
• $n = 72 m + 12$ の時、$S_n$ は $433$ で割り切りれる
• $n = 360 m + 192$ の時、$S_n$ は $31$ で割り切りれる
• $n = 360 m + 48$ の時、$S_n$ を割り切る素数は見つからなかった
• $n = 360 m + 120$ の時、$S_n$ を割り切る素数は見つからなかった
• $n = 360 m + 264$ の時、$S_n$ を割り切る素数は見つからなかった
• $n = 360 m + 336$ の時、$S_n$ を割り切る素数は見つからなかった

今回チェック（整理）した中では一番大きな素数(433)で割り切れたもの、その１。

k=163187 の場合

$ ./target/release/sierpinski-number-rs --max-a 10000 163187 | grep '^--'
-- 1/2 = 50%
-- 3/4 = 75%
-- 11/12 = 91.66666666666666%
-- 23/24 = 95.83333333333334%
-- 70/72 = 97.22222222222221%
-- 351/360 = 97.5%
-- 494/504 = 98.01587301587301%
-- 2475/2520 = 98.21428571428571%

• $n = 2 m + 0$ の時、$S_n$ は $3$ で割り切りれる
• $n = 4 m + 1$ の時、$S_n$ は $5$ で割り切りれる
• $n = 12 m + 7$ の時、$S_n$ は $7$ で割り切りれる
• $n = 12 m + 11$ の時、$S_n$ は $13$ で割り切りれる
• $n = 24 m + 3$ の時、$S_n$ は $241$ で割り切りれる
• $n = 72 m + 39$ の時、$S_n$ は $433$ で割り切りれる
• $n = 72 m + 15$ の時、$S_n$ を割り切る素数は見つからなかった
• $n = 72 m + 63$ の時、$S_n$ を割り切る素数は見つからなかった

今回チェック（整理）した中では一番大きな素数(433)で割り切れたもの、その２。

k=200749 の場合

$ ./target/release/sierpinski-number-rs --max-a 10000 200749 | grep '^--'
-- 1/2 = 50%
-- 3/4 = 75%
-- 7/8 = 87.5%
-- 11/12 = 91.66666666666666%
-- 23/24 = 95.83333333333334%
-- 70/72 = 97.22222222222221%
-- 352/360 = 97.77777777777777%
-- 1057/1080 = 97.87037037037038%
-- 1762/1800 = 97.88888888888889%
-- 3880/3960 = 97.97979797979798%
-- 5291/5400 = 97.98148148148148%

• $n = 2 m + 1$ の時、$S_n$ は $3$ で割り切りれる
• $n = 4 m + 0$ の時、$S_n$ は $5$ で割り切りれる
• $n = 8 m + 6$ の時、$S_n$ は $17$ で割り切りれる
• $n = 12 m + 2$ の時、$S_n$ は $13$ で割り切りれる
• $n = 72 m + 18$ の時、$S_n$ は $73$ で割り切りれる
• $n = 72 m + 42$ の時、$S_n$ を割り切る素数は見つからなかった
• $n = 72 m + 66$ の時、$S_n$ を割り切る素数は見つからなかった

k=209611 の場合

$ ./target/release/sierpinski-number-rs --max-a 10000 209611 | grep '^--'
-- 1/2 = 50%
-- 3/4 = 75%
-- 7/8 = 87.5%
-- 11/12 = 91.66666666666666%
-- 23/24 = 95.83333333333334%
-- 70/72 = 97.22222222222221%
-- 117/120 = 97.5%
-- 354/360 = 98.33333333333333%
-- 1063/1080 = 98.42592592592592%
-- 2484/2520 = 98.57142857142858%
-- 7458/7560 = 98.65079365079366%

• $n = 2 m + 1$ の時、$S_n$ は $3$ で割り切りれる
• $n = 4 m + 2$ の時、$S_n$ は $5$ で割り切りれる
• $n = 8 m + 4$ の時、$S_n$ は $17$ で割り切りれる
• $n = 12 m + 0$ の時、$S_n$ は $13$ で割り切りれる
• $n = 12 m + 4$ の時、$S_n$ は $7$ で割り切りれる
• $n = 72 m + 32$ の時、$S_n$ は $19$ で割り切りれる
• $n = 72 m + 8$ の時、$S_n$ を割り切る素数は見つからなかった
• $n = 72 m + 56$ の時、$S_n$ を割り切る素数は見つからなかった

k=222113 の場合

$ ./target/release/sierpinski-number-rs --max-a 10000 222113 | grep '^--'
-- 1/2 = 50%
-- 3/4 = 75%
-- 7/8 = 87.5%
-- 22/24 = 91.66666666666666%
-- 37/40 = 92.5%
-- 67/72 = 93.05555555555556%
-- 115/120 = 95.83333333333334%
-- 348/360 = 96.66666666666667%
-- 2448/2520 = 97.14285714285714%

• $n = 2 m + 0$ の時、$S_n$ は $3$ で割り切りれる
• $n = 4 m + 3$ の時、$S_n$ は $5$ で割り切りれる
• $n = 8 m + 1$ の時、$S_n$ は $17$ で割り切りれる
• $n = 24 m + 13$ の時、$S_n$ は $7$ で割り切りれる
• $n = 24 m + 5$ の時、$S_n$ を割り切る素数は見つからなかった
• $n = 24 m + 21$ の時、$S_n$ を割り切る素数は見つからなかった

k=225931 の場合

$ ./target/release/sierpinski-number-rs --max-a 10000 225931 | grep '^--'
-- 1/2 = 50%
-- 3/4 = 75%
-- 7/8 = 87.5%
-- 11/12 = 91.66666666666666%
-- 23/24 = 95.83333333333334%
-- 70/72 = 97.22222222222221%
-- 117/120 = 97.5%
-- 354/360 = 98.33333333333333%
-- 2484/2520 = 98.57142857142858%

• $n = 2 m + 1$ の時、$S_n$ は $3$ で割り切りれる
• $n = 4 m + 2$ の時、$S_n$ は $5$ で割り切りれる
• $n = 8 m + 4$ の時、$S_n$ は $17$ で割り切りれる
• $n = 12 m + 0$ の時、$S_n$ は $7$ で割り切りれる
• $n = 12 m + 4$ の時、$S_n$ は $13$ で割り切りれる
• $n = 72 m + 8$ の時、$S_n$ は $19$ で割り切りれる
• $n = 72 m + 32$ の時、$S_n$ を割り切る素数は見つからなかった
• $n = 72 m + 56$ の時、$S_n$ を割り切る素数は見つからなかった

k=227723 の場合

$ ./target/release/sierpinski-number-rs --max-a 10000 227723 | grep '^--'
-- 1/2 = 50%
-- 3/4 = 75%
-- 7/8 = 87.5%
-- 11/12 = 91.66666666666666%
-- 23/24 = 95.83333333333334%
-- 70/72 = 97.22222222222221%
-- 352/360 = 97.77777777777777%
-- 3522/3600 = 97.83333333333334%
-- 4584/4680 = 97.94871794871794%

• $n = 2 m + 0$ の時、$S_n$ は $3$ で割り切りれる
• $n = 4 m + 3$ の時、$S_n$ は $5$ で割り切りれる
• $n = 8 m + 1$ の時、$S_n$ は $17$ で割り切りれる
• $n = 12 m + 5$ の時、$S_n$ は $13$ で割り切りれる
• $n = 12 m + 9$ の時、$S_n$ は $7$ で割り切りれる
• $n = 72 m + 37$ の時、$S_n$ は $73$ で割り切りれる
• $n = 72 m + 13$ の時、$S_n$ を割り切る素数は見つからなかった
• $n = 72 m + 61$ の時、$S_n$ を割り切る素数は見つからなかった

k=229673 の場合

$ ./target/release/sierpinski-number-rs --max-a 10000 229673 | grep '^--'
-- 1/2 = 50%
-- 3/4 = 75%
-- 11/12 = 91.66666666666666%
-- 35/36 = 97.22222222222221%
-- 177/180 = 98.33333333333333%
-- 1240/1260 = 98.4126984126984%
-- 1596/1620 = 98.51851851851852%
-- 1954/1980 = 98.68686868686869%

• $n = 2 m + 0$ の時、$S_n$ は $3$ で割り切りれる
• $n = 4 m + 3$ の時、$S_n$ は $5$ で割り切りれる
• $n = 12 m + 1$ の時、$S_n$ は $7$ で割り切りれる
• $n = 12 m + 5$ の時、$S_n$ は $13$ で割り切りれる
• $n = 36 m + 9$ の時、$S_n$ は $19$ で割り切りれる
• $n = 36 m + 21$ の時、$S_n$ は $37$ で割り切りれる
• $n = 180 m + 33$ の時、$S_n$ は $11$ で割り切りれる
• $n = 180 m + 105$ の時、$S_n$ は $41$ で割り切りれる
• $n = 180 m + 69$ の時、$S_n$ を割り切る素数は見つからなかった
• $n = 180 m + 141$ の時、$S_n$ を割り切る素数は見つからなかった
• $n = 180 m + 177$ の時、$S_n$ を割り切る素数は見つからなかった

k=237019 の場合

$ ./target/release/sierpinski-number-rs --max-a 10000 237019 | grep '^--'
-- 1/2 = 50%
-- 3/4 = 75%
-- 11/12 = 91.66666666666666%
-- 35/36 = 97.22222222222221%
-- 176/180 = 97.77777777777777%
-- 1234/1260 = 97.93650793650794%
-- 4056/4140 = 97.97101449275362%
-- 8642/8820 = 97.98185941043084%

• $n = 2 m + 1$ の時、$S_n$ は $3$ で割り切りれる
• $n = 4 m + 0$ の時、$S_n$ は $5$ で割り切りれる
• $n = 12 m + 2$ の時、$S_n$ は $13$ で割り切りれる
• $n = 12 m + 6$ の時、$S_n$ は $7$ で割り切りれる
• $n = 36 m + 10$ の時、$S_n$ は $37$ で割り切りれる
• $n = 36 m + 22$ の時、$S_n$ は $19$ で割り切りれる
• $n = 180 m + 34$ の時、$S_n$ は $11$ で割り切りれる
• $n = 180 m + 70$ の時、$S_n$ を割り切る素数は見つからなかった
• $n = 180 m + 106$ の時、$S_n$ を割り切る素数は見つからなかった
• $n = 180 m + 142$ の時、$S_n$ を割り切る素数は見つからなかった
• $n = 180 m + 178$ の時、$S_n$ を割り切る素数は見つからなかった

k=238411 の場合

$ ./target/release/sierpinski-number-rs --max-a 10000 238411 | grep '^--'
-- 1/2 = 50%
-- 3/4 = 75%
-- 11/12 = 91.66666666666666%
-- 34/36 = 94.44444444444444%
-- 172/180 = 95.55555555555556%
-- 862/900 = 95.77777777777777%
-- 2246/2340 = 95.98290598290599%
-- 2940/3060 = 96.07843137254902%

• $n = 2 m + 1$ の時、$S_n$ は $3$ で割り切りれる
• $n = 4 m + 2$ の時、$S_n$ は $5$ で割り切りれる
• $n = 12 m + 4$ の時、$S_n$ は $13$ で割り切りれる
• $n = 12 m + 7$ の時、$S_n$ は $3$ で割り切りれる
• $n = 36 m + 0$ の時、$S_n$ は $19$ で割り切りれる
• $n = 36 m + 12$ の時、$S_n$ を割り切る素数は見つからなかった
• $n = 36 m + 24$ の時、$S_n$ を割り切る素数は見つからなかった