素数与第素数个素数的和能生成$10^9$内的所有偶数

加性组合中,两个集合 \(A\)\(B\)加法集和集 \(A+B\) 定义为\(A\)中任意元素 \(a_i\)\(B\) 中任意元素 \(b_j\) 之和 \(a_i+b_j\) 构成的集合,用 \(|A|\) 表示集合 \(A\) 中元素的数量,当 \(A\)\(B\) 都不为空集时($ |A|\cdot|B|>0$),有不等式

\[|A|+|B|-1\le |A+B|\le |A|\cdot|B| \]

\(n\)以内素数的数量 \(|P(n)|\simeq\frac{n}{\log n}\),根据哥德巴赫猜想,所有4以上的偶数都可表示为两个素数之和,这至少意味着素数集和集的元素数量 \(|P+P|\simeq n\)。事实上这是一个比较宽松的猜想,即使取素数集中的一个子集就有可能覆盖所有偶数,例如根据杜伯纳猜想,所有4208以上的偶数都能表示成两个孪生素数之和,这意味着\(n\)以内孪生素数的数量至少达到了\(\sqrt{n}\)

那么,能不能用整个素数集与另一个更小的集合求和集,来覆盖偶数集呢?最优情况是选一个 \(n\) 以内元素数量只有 \(\log n\) 的集合(类似等比数列),使得达到和集元素数量的理论上限。但经过部分程序验证,单独的等比数列 \(a_{i+1}=a_iq\) 和类等比递推数列 \(a_{i+1}=a_iq+d\) 是不行的,也许几个等比数列的组合可以,待继续验证。

在探究过程中,一个新的发现是素数集
P=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43...]
和第素数个素数构成的集合
PP=[3, 5, 11, 17, 31, 41, 59, 67, 83, 109, 127, ...]
的和集 \(P+PP\) 可生成 \([6,10^9]\) 的全部偶数,更大范围由于本人的电脑原因尚未验证。感觉这个发现比较有价值,特发出来让大家一起讨论。

本人编程所用的Python代码如下:

from time import time

def getPrimeSet_List_isPrime(n=10**6):
    """
    同时生成n以内的素数集合方便查找、isPrime数组方便o(1)查找、primeList方便遍历
    """
    n=max(2,n+1)
    isPrime=[True]*n
    isPrime[0]=False
    isPrime[1]=False
    for i in range(1,n,1):
        if isPrime[i]:
            for j in range(i*i,n,i):
                isPrime[j]=False
    primeList=[i for i in range(n) if isPrime[i]]
    primeSet=set(primeList)
    return primeSet,primeList,isPrime

def 素数集与第素数个素数的和集能否覆盖n以内所有奇数或偶数(n=10**3,idxOffset=-1):
    """
    验证素数集与第素数个素数的和集能覆盖多少奇数、偶数
    n     idxOffset  奇数未覆盖率  偶数未覆盖率  未覆盖偶数  耗时
    10^7  -1               1          4e-7     [2,4]      18s
    """
    primeSet,primeList,isPrime=getPrimeSet_List_isPrime(n)
    print(f"{n=},{idxOffset=}")
    print(f"primeList={primeList[:50]}")
    pprimes=[primeList[i+idxOffset] for i in primeList if i+idxOffset<len(primeList)]
    print(f"primeprimeList={pprimes[:50]}")
    isCovered=[False]*(n+1)
    print("逐项集合查找法\n未覆盖的偶数:")
    pn=idxv=len(primeList)
    for e in range(2,n+1,2):
        for idx in primeList:
            if idx+idxOffset>=pn or primeList[idx+idxOffset]>e:
                break
            v=e-primeList[idx+idxOffset]
            if v in primeSet:
                isCovered[e]=True
                break
        if not isCovered[e]:
            print(e,end=",")
    print()
    uncoverdOddNums=[i for i in range(1,n+1,2) if isCovered[i]==False]
    uncoverdEvenNums=[i for i in range(2,n+1,2) if isCovered[i]==False]
    print(f"未覆盖偶数:{uncoverdEvenNums[:50]}...{uncoverdEvenNums[-50:]}")
    print(f"奇数未覆盖率{len(uncoverdOddNums)*2/n},偶数未覆盖率{len(uncoverdEvenNums)*2/n}")
    return uncoverdOddNums,uncoverdEvenNums

if __name__=="__main__":
    startTime=time()
    素数集与第素数个素数的和集能否覆盖n以内所有奇数或偶数()
    print(f"运行时间{time()-startTime}s")

刚开始程序采用双重循环暴力遍历,时间复杂度约为\(O\left(\frac{n^2}{(\log n)^3}\right)\),验证到 \(n=10^6\) 时程序运行时间已达2分钟;当前版本改用了逐项遍历偶数,用集合快速查询,时间复杂度没变,但验证完 \(10^7\) 内的偶数只需18秒。移植到C++后,效率更快,分别在3秒、8分钟内验证完\(10^7\)\(10^9\)内的偶数。C++代码如下:

#include<vector>
#include<iostream>
#include<cmath>
#include<unordered_set>
using namespace std;
using ull=unsigned long long;
void printVector(vector<ull>&arr,ull startIdx=0,ull maxLen=50){
    cout<<"{";
    for(ull i=fmax(0,startIdx);i<fmin(arr.size(),startIdx+maxLen);i++){
        cout<<arr[i]<<",";
    }
    cout<<"};"<<endl;
    return;
}

vector<ull>genePrimeList(ull n=1e+6){
    n++;
    vector<bool>isPrime(n,true);
    vector<ull>primeList;
    for(ull i=2;i<n;i++){
        if(isPrime[i]){
                primeList.emplace_back(i);
            for(ull j=i*i;j<n;j+=i){
                isPrime[j]=false;
            }
        }
    }
    return primeList;
}

vector<ull>primesAndPrimeOfPrimeIndexCoverEvenNumber(ull n=1e+6,int indexOffset=-1){
    /**
    n是查找范围上限
    indexOffset调整第素数个素数的索引,使变成第(素数+indexOffset)个素数
    10^9内,只有【2,4】未被覆盖,运行耗时8min25s
    */
    cout<<"n="<<n<<",indexOffset="<<indexOffset<<endl;
    vector<bool>isCovered(n+1,false);
    vector<ull>primeList=genePrimeList(n),pprimes;
    unordered_set<ull>primeSet(primeList.begin(),primeList.end());
    cout<<"primeList="<<endl;
    printVector(primeList);
    ull pn=primeList.size();
    ull val;
    cout<<"primesAndPrimeOfPrimeIndexCoverEvenNumber - set search\n uncoverd Even Nums=\n";
    for(ull e=2;e<=n;e+=2){
        for(auto idx:primeList){
            if(idx+indexOffset>=pn || e<=primeList[idx+indexOffset]){
                break;
            }
            val=e-primeList[idx+indexOffset];
            if(primeSet.find(val)!=primeSet.end()){
                isCovered[e]=true;
                break;
            }
        }
        if(isCovered[e]==false){
            cout<<e<<",";
        }
    }
    cout<<endl;
    vector<ull>uncoveredEvenNumber;
    for(ull i=2;i<=n;i+=2){
        if(isCovered[i]==false){
            uncoveredEvenNumber.emplace_back(i);
        }
    }
    cout<<"uncoveredEvenNumber head="<<endl;
    printVector(uncoveredEvenNumber);
    cout<<"uncoveredEvenNumber end="<<endl;
    printVector(uncoveredEvenNumber,uncoveredEvenNumber.size()-50);
    return uncoveredEvenNumber;
}

int main(){
    int n=1e+9;
    primesAndPrimeOfPrimeIndexCoverEvenNumber(n);
    return 0;
}

\(n\)每增加一个数量级,程序运行耗时百倍增长,后边也许可以用多线程加速一下,由于电脑性能与算法复杂度原因,个人验证更大的偶数的空间已经不太大了,希望大家讨论一下有没有时间复杂度更低的算法,或者用更好的电脑帮忙验证一下对于 \(10^9\) 以上的大偶数,这个猜想(每个 \(4\) 以上的偶数可以表示为一个素数和一个“第素数个素数”之和)是否仍正确。

也许这个猜想已经有人以前说过了,有知道的的话麻烦说一下;这个猜想表述如此简单,被前人讨论过的几率还是挺大的。

即使最终被验证在更大范围内不正确,也已经是个有趣的巧合了。

热门相关:混在三国当军阀   龙组使命   总裁大人,又又又吻我了   榴绽朱门   楚汉争鼎