寝癖頭の解法

小学生の目線から、勉強中の覚え書きを投稿、更新していきます。

双子素数について

双子素数についての話です。
きっかけは、AIZU ONNLINE JUDGEのVolume1 - 0150から、"Twin Prime"の出題でした。
https://onlinejudge.u-aizu.ac.jp/problems/0150

まずは双子素数について、Wikipediaによれば...
>双子素数(英: twin prime)とは、差が 2 である二つの素数の組を構成する各素数のことである。双子素数の組は、(2, 3) を除いた、最も近い素数の組である。
https://ja.wikipedia.org/wiki/双子素数
>素数が無数に存在することは古代ギリシアで既に分かっており、ユークリッドの『原論』に証明がある。
>これに対し、双子素数は無数に存在するかという問題、いわゆる「双子素数の予想」や「双子素数の問題」は、いまだに数学上の未解決問題である。
出た、ユークリッド
来た、未解決問題。
最近よく見かけるわー。
ちな、数学の参考書とかで言うと、単元の頭とか例題と一緒に示されるのが定理で、その解決前、つまりまだ証明されていない問題が予想になります。

で、双子素数の性質について...
>(3, 5) を除く全ての双子素数は (6n − 1, 6n + 1)(n は自然数)の形である。
>最初の2組を除き、双子素数の一の位は(十進法で)(1, 3), (7, 9), (9, 1) のいずれかである。
要するに、(3, 5) を除いた、差が 2 である二つの素数の組、すなわち双子素数は、6の倍数を挟む形にしかならないと言うわけです。

そして、AIZU ONLINE JUDGEのVolume1 - 0150から、"Twin Prime"の出題では...
双子素数を構成する素数のうち大きい素数をその双子素数の大きさと呼ぶことにします。
「入力された整数 n 以下の双子素数で大きさが最大のものを出力するプログラムを作成してください」
はい、わかりましたー。

僕が作成、提出したコードは、以下のとおりです。

Aizu Online Judge in C++ #Volume1 - 0150 : Twin Prime
/*
Aizu Online Judge in C++ #Volume1 - 0150 : Twin Prime
https://onlinejudge.u-aizu.ac.jp/problems/0150
 提出コードの解答例
 https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
int main(void){
    while(1){
        int n;
        cin>>n;
        if(n==0){
            return 0;
        }
        vector<bool> is_prime;
        is_prime.resize(n+1,true);
        is_prime[0]=false;
        is_prime[1]=false;
        for(int i=2;i<=n;i++){
            if(is_prime[i]==true){
                for(int j=2;i*j<=n;j++){
                    is_prime[i*j]=false;
                }
            }
        }
        int m=-1;
        for(int i=0;i<=n;i++){
            if(i+2<=n && (is_prime[i] && is_prime[i+2])){
                m=max(m,i+2);
            }
        }
        cout<<m-2<<" "<<m<<endl;
    }
}

それから、双子素数の逆数和について...
>p と p + 2 がともに素数の場合、次式は収束する。
f:id:neguse_atama:20211006024816p:plain
>この値 (1.90強) をブルン定数と呼ぶ。
>素数の逆数和は発散するので、素数の中で双子素数は、さほど多くはないといえる。
https://ja.wikipedia.org/wiki/ブルン定数

あと、双子素数に類似する素数の組としては...
・セクシー素数(sexy primes)
>差が 6 の素数の組 (p, p + 6) である。
>最小のセクシー素数は (5, 11) である。
>もし p + 2 または p + 4 も素数であれば、そのセクシー素数三つ子素数の一部となる。

・いとこ素数
>差が 4 である素数の組である。
>2組のいとこ素数に属するのは7だけである。
>(n, n+4, n+8)は、どれかひとつは必ず3で割り切れてしまうため、3者とも素数であるのはn=3の場合のみである。

三つ子素数(prime triplet)
>3個の素数の組で、(p, p + 2, p + 6) または (p, p + 4, p + 6) のタイプのもののことである。

で、三つ子素数は双子素数、いとこ素数、セクシー素数を含みます。

・四つ子素数(prime quadruplet)
>4個の素数の組で、(p, p + 2, p + 6, p + 8) のタイプのもののことをいう。
さらに、四つ子素数について、p − 4 または p + 12 がさらに素数であれば、それらを加えた5つ組を五つ子素数(prime quintuplet)と言って、 p − 4 と p + 12 の両方が素数であれば、その6つ組を六つ子素数(prime sextuplet)と言います。

その他の形と「七つ子」以上については...
>p − 2 および p + 10 は必ず 3 の倍数であるため、これらを含んだ「五つ子」は (p − 2, p, p + 2, p + 6, p + 8) の形の (3, 5, 7, 11, 13) しか存在しない。
>また、p − 6, p + 14 はいずれも 5 の倍数になるため、双子素数3つからなる (p, p + 2, p + 6, p + 8, p + 12, p + 14) の形の「六つ子」は、(5, 7, 11, 13, 17, 19) しか存在しない。
>さらに p − 8, p + 16 はいずれも 3 の倍数になるため、六つ子素数の両端±4の範囲には素数はない。
>(3, 5, 7, 11, 13, 17, 19), (5, 7, 11, 13, 17, 19, 23) の「七つ子」、(3, 5, 7, 11, 13, 17, 19, 23) の「八つ子」を除いて、差が4以内で連なる七つ子以上の素数の組は存在しない。

はい、とても勉強になりましたー。
でも、なんか疲れちゃいました...組だけでも、もっとあるみたいだし。
ってか、素数の分類、多すぎだよー。
それ自体がもう問題だわーって、思いました。

設問の出典は、プログラミング問題のオンライン採点システム「Aizu Online Judge(AOJ)」です。
http://judge.u-aizu.ac.jp/onlinejudge/