{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R734",
  "content_hash": null,
  "slug": "sps101-artifact-witness-and-size-ten-exhaustion",
  "type": "artifact",
  "title": "Exact witness replay and exhaustive ten-mark exclusion",
  "summary": "A deterministic C++ program checks both 45-element images and exhausts every normalized ten-mark candidate.",
  "relevance": "This supplies a computation, dataset, or executable check used to assess the target problem.",
  "relevance_source": "derived",
  "body": "Multiplying a field set by a nonzero scalar preserves both Sidon conditions. On exponents this translates the set in \\(\\mathbf Z/100\\mathbf Z\\), so any hypothetical ten-mark set may be normalized to contain 0. The depth-first search lists its remaining marks in increasing order.\n\nAt each node, two 100-bit masks record the directed differences already used. Appending a mark \\(x\\) is allowed exactly when the residues \\(x-b\\) and \\(b-x\\), for every earlier mark \\(b\\), are new and mutually distinct. The only pruning step checks whether enough larger residues remain. The program therefore visits every normalized candidate that could extend to ten marks.\n\nThe depth-node totals for selected-set sizes 1 through 10 are\n\\[\n1,90,3926,103470,1643822,13706516,43175690,25432298,526256,0.\n\\]\nTheir sum is 84,592,069. No node reaches size 10. The same program evaluates all unordered pairs of the displayed field witness and obtains two images of size 45. Its exact standard output has SHA-256 digest `3133bddeeb7e4795c774e85e9b699aaf940ec5e0009ba73ab9860a4113cf4e0d`.",
  "status": "available",
  "evidence_grade": "executable",
  "scope": {
    "kind": "bounded",
    "statement": "the displayed nine-element witness and every normalized ten-mark subset of Z/100Z",
    "bounds": {
      "field_order": {
        "min": 101,
        "max": 101
      },
      "cyclic_group_order": {
        "min": 100,
        "max": 100
      },
      "candidate_mark_count": {
        "min": 10,
        "max": 10
      },
      "partial_nodes": {
        "min": 84592069,
        "max": 84592069
      }
    },
    "exhaustive": true
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "partial",
    "kind": "inline_cpp_computation",
    "entrypoint": "join source_lines with newline, compile using c++ -O3 -std=c++17, and run",
    "runtime": "C++17 standard library",
    "citation": {
      "url": "https://doi.org/10.26493/1855-3974.2374.9ff",
      "locator": "Inline C++17 computation executed on 2026-07-25"
    },
    "outputs": "witness=1,11,47,62,67,70,71,84,96 pairs=45 sum_image=45 product_image=45\ndepth_nodes=1,90,3926,103470,1643822,13706516,43175690,25432298,526256,0 total_nodes=84592069 size10=0\n",
    "inline_source": [
      "#include <algorithm>",
      "#include <cstdint>",
      "#include <iostream>",
      "#include <set>",
      "#include <vector>",
      "using namespace std;",
      "uint64_t lo=0, hi=0;",
      "int B[10];",
      "unsigned long long nodes[11]={};",
      "int pow2v[100];",
      "bool has(int r){return r<64 ? (lo>>r)&1ULL : (hi>>(r-64))&1ULL;}",
      "void put(int r){if(r<64)lo|=1ULL<<r;else hi|=1ULL<<(r-64);}",
      "void del(int r){if(r<64)lo&=~(1ULL<<r);else hi&=~(1ULL<<(r-64));}",
      "bool dfs(int depth,int start){",
      "  nodes[depth]++;",
      "  if(depth==10) return true;",
      "  if(100-start < 10-depth)return false;",
      "  for(int x=start;x<=100-(10-depth);x++){",
      "    int vals[18],n=0;bool ok=true;",
      "    for(int i=0;i<depth;i++){",
      "      int d=(x-B[i]+100)%100, e=(B[i]-x+100)%100;",
      "      if(d==e||has(d)||has(e)){ok=false;break;}",
      "      for(int z=0;z<n;z++)if(vals[z]==d||vals[z]==e){ok=false;break;}",
      "      if(!ok)break; vals[n++]=d; vals[n++]=e;",
      "    }",
      "    if(!ok)continue;",
      "    for(int i=0;i<n;i++)put(vals[i]);B[depth]=x;",
      "    if(dfs(depth+1,x+1))return true;",
      "    for(int i=0;i<n;i++)del(vals[i]);",
      "  }",
      "  return false;",
      "}",
      "int main(){",
      "  int v=1;for(int e=0;e<100;e++){pow2v[e]=v;v=v*2%101;}",
      "  const int witness[9]={1,11,47,62,67,70,71,84,96};",
      "  set<int> sums,products;",
      "  for(int i=0;i<9;i++)for(int j=i;j<9;j++){",
      "    sums.insert((witness[i]+witness[j])%101);",
      "    products.insert(witness[i]*witness[j]%101);",
      "  }",
      "  if(sums.size()!=45 || products.size()!=45) return 2;",
      "  if(v!=1 || pow2v[20]==1 || pow2v[50]==1) return 3;",
      "  B[0]=0; bool found=dfs(1,1);",
      "  if(found) return 4;",
      "  unsigned long long total=0;",
      "  for(int i=1;i<=10;i++) total+=nodes[i];",
      "  cout<<\"witness=1,11,47,62,67,70,71,84,96\"",
      "      <<\" pairs=45 sum_image=\"<<sums.size()<<\" product_image=\"<<products.size()<<'\\n';",
      "  cout<<\"depth_nodes=\";",
      "  for(int i=1;i<=10;i++){if(i>1)cout<<',';cout<<nodes[i];}",
      "  cout<<\" total_nodes=\"<<total<<\" size10=0\\n\";",
      "}"
    ],
    "missing": [
      "command"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://doi.org/10.26493/1855-3974.2374.9ff",
    "locator": "Inline C++17 computation executed on 2026-07-25"
  },
  "models": [],
  "continuation": null,
  "relations": [
    {
      "slug": "R736",
      "title": "The exact maximum is 9",
      "object_type": "claim",
      "relation": "verifies",
      "direction": "outgoing"
    },
    {
      "slug": "simultaneous-sum-product-sidon-f101",
      "title": "simultaneous sum product sidon f101",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}