ゴールドバッハ予想についての話です。
きっかけは、paizaラーニングのレベルアップ問題集「素数メニュー」からの出題でした。
paiza.jp
ゴールドバッハ予想とは、Wikipediaによれば...
「全ての 2 よりも大きな偶数は2つの素数の和として表すことができる」
この予想は、4 × 10^18 までの全ての偶数について成り立つことがコンピュータによって確かめられていて、一般に正しいと想定されているが、まだ証明されていないそうです。
ja.wikipedia.org
予想には、ほとんど同値ないくつかの述べ方があり、次のように述べることが多い:
・4以上の全ての偶数は、二つの素数の和で表すことができる。
・6以上の全ての偶数は、二つの奇素数の和で表すことができる。(4=2+2:偶素数同士の和)
このとき、同じ素数を2度使っても良いものとする。
ゴールドバッハ予想と呼ばれるのは、1742年6月7日にクリスティアン・ゴールドバッハがレオンハルト・オイラーへの手紙で述べた、上と同値な次のような予想について...
「5より大きな任意の自然数は、三つの素数の和で表せる」
これから上が導けるのは、偶数を三つの素数の和で表すと素数の一つは 2 になっているからで、たしかに題意は同じと考えられます。
・奇数+奇数+奇数=奇数
・和が偶数になるには、奇数+奇数+偶数 or 偶数+偶数+偶数
そして、paizaラーニングのレベルアップ問題集「素数メニュー」の出題では...
「全ての 3 よりも大きな偶数は 2 つの素数の和として表すことができる」
として、「10^5 以下の偶数 N が与えられるので、 N を 2 つの素数の和で表し、出力してください」という出題でした。
なるほど、面白い、やろう!
僕が作成、提出したコードは、以下のとおりです。
/* C++による「素数メニュー」問題集 ゴールドバッハ予想 https://paiza.jp/works/mondai 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; bool prime(ll n){ for(ll i=2;i<=sqrt(n);i++){ if(n%i==0){ return false; } } return true; } int main(void){ ll n; cin>>n; vector<pair<ll,ll>> v; vector<ll> vi; for(ll i=2;i<n;i++){ if(prime(i)==true){ if(prime(n-i)==true){ v.push_back(pair(i*(n-i),i)); } } } sort(v.rbegin(),v.rend()); ll ans=v[0].second; if(ans>n-ans){ cout<<n-ans<<endl; cout<<ans<<endl; }else{ cout<<ans<<endl; cout<<n-ans<<endl; } return 0; }
「ただし、答えが複数個ある場合は、それらのうち、積が最も大きくなるような 2 つの素数を出力してください」
(答えは 1 通りになることが保証されます)
類似の予想としては、「弱いゴールドバッハ予想」というものがあって...
「5より大きい奇数は三つの素数の和で表せる」
論理的に、4より大きい偶数が二つの奇素数の和で表せるという「強いゴールドバッハ予想」が正しいならば、弱いゴールドバッハ予想も真(正しい)となるわけです。
このような「ならば」は、含意(implication)と呼ばれて、含意の命題「AならばB(" A only if B")」を記号で表すと、「A⇒B」と書ける、数学における定理の基本形です。
paizaラーニングのレベルアップ問題集については、ユーザー同士で解答を教え合ったり、コードを公開したりするのは自由としています。
また授業や研修、教材などにも利用できるそうです。