置換可能素数

レピュニットからの続き

プログラミングの例題として次のようなことを考えた。「ある素数があって，その各桁を入れ換えてできる全ての数が素数になるものを考える。その最大の素数はどんなものだろうか。」

で，実際に自分でプログラムを書くかというと，それは面倒なので，いつものようにAIに頼ることにする。軟弱だ。脳細胞のフレイルだ。OpenAI o1とかPerlexity Proに頼ってみたが，正しい答えがでない。PythonをJuliaに書き換えても，さらにドツボにはまるだけ。

一度リセットしてから，再度挑戦した。

Ｑ（koshix）：

n桁の素数が与えられたとき，その各桁の数字を入れ替えてできるすべての数が再び素数になるようなもので，できるだけ大きな数を探したい。桁数nを与えたときに，この条件を満たす最大の数を求めるプログラムを作成してください。

Ａ（Perplexity Pro）：

この問題を解決するために、以下のようなプログラムを作成しました。このプログラムは、与えられた桁数nに対して、条件を満たす最大の素数を見つけます。

import itertools

from sympy import isprime

def find_large_permutational_prime(n):

    lower_bound = 10**(n-1)

    upper_bound = 10**n

    primes = [p for p in range(lower_bound, upper_bound) if isprime(p)]

    largest_permutational_prime = -1

    for prime in primes:

        permutations = set(int(''.join(p)) for p in itertools.permutations(str(prime)))

        if all(isprime(p) for p in permutations):

            largest_permutational_prime = max(largest_permutational_prime, prime)

    return largest_permutational_prime

そして，ChatGPT-4oでJuliaに変換したものが次の通りである。

using Primes

using Combinatorics

function find_large_permutational_prime(n)

    lower_bound = 10^(n - 1)

    upper_bound = 10^n - 1

    largest_permutational_prime = -1

    

    for prime in primes(lower_bound, upper_bound)

        perms = Set(parse(Int, join(p)) for p in Combinatorics.permutations(string(prime)))

        if all(isprime(p) for p in perms)

            largest_permutational_prime = max(largest_permutational_prime, prime)

        end

    end

    

    return largest_permutational_prime

end

これを実行すると，n=3で991が得られる。n=4,5,6では結果なしということになった。これから，nが4以上では条件を満たす素数が存在しないと証明できないかと考えたけれど，そんな簡単な話ではなかった。もちろん，現在の生成AIでは証明できない。

調べてみるとこのような素数は，置換可能素数として既によく知られているものだった。911の上にある素数はレピュニット素数だった。これは無限個あると推定されているがまだよくわかっていないのだ。もちろん，3,7,9 の1種類だけが並んだ数は素数にはならない。