{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R428",
  "content_hash": null,
  "slug": "kmmp-artifact-search-and-cycle-replay",
  "type": "artifact",
  "title": "Exact 4,096-start search and record-cycle replay",
  "summary": "ISO C reproduces every sampled period, checks primality, verifies the record's first return, and hashes both the search records and cycle trace.",
  "relevance": "For Longest cycle of a nonlinear area-preserving map over F_1000003, record kmmp-artifact-search-and-cycle-replay (“Exact 4,096-start search and record-cycle replay”) supplies evidence or a replay used to check the packet. The record states: ISO C reproduces every sampled period, checks primality, verifies the record's first return, and hashes both the search records and cycle trace.",
  "relevance_source": "recorded",
  "body": "Starting with the 64-bit seed `6b69636b65646d61`, two consecutive SplitMix64 outputs reduced modulo \\(p\\) give each sampled \\((x,y)\\). The program computes the first return for every index 0 through 4095. It hashes each four-tuple \\((i,x,y,\\ell)\\), with all fields encoded as little-endian unsigned 64-bit integers. The final search digest is `f6dd5727b5ac0b50`.\n\nThe record advances at indices 0, 6, 66, and 234, with periods 4,135,917; 4,897,828; 8,743,054; and 11,656,512. The search was reproduced in four consecutive 1,024-index batches. Carrying the FNV state across the batch boundaries gave cumulative digests `f2906540ab7a26e8`, `b69b9b82a87dbe89`, `d042bfc2f97c70da`, and `f6dd5727b5ac0b50`.\n\nThe witness replay checks every intermediate state against the start. Selected states are \\((6790,451908)\\) at time 100, \\((693931,696803)\\) at time 1,000, \\((494671,78205)\\) at time 1,000,000, \\((385219,565829)\\) at time 5,000,000, and \\((42331,466469)\\) at time 10,000,000. Time 11,656,511 gives the predecessor \\((223804,39277)\\), and the next update returns to the start. The six canonical stdout lines, including their terminating line feeds, have SHA-256 digest `8eeeee9564e2e5badd30d7d6825dc6e6ba5784592362b457ca464197b2b68180`.",
  "status": "available",
  "evidence_grade": "executable",
  "scope": {
    "kind": "bounded",
    "statement": "all 4096 SplitMix64-generated starting states with indices 0 through 4095 at p=1000003, followed by every state in the record cycle",
    "bounds": {
      "prime": {
        "min": 1000003,
        "max": 1000003
      },
      "sample_index": {
        "min": 0,
        "max": 4095
      },
      "sampled_starts": {
        "min": 4096,
        "max": 4096
      },
      "record_cycle_updates": {
        "min": 11656512,
        "max": 11656512
      }
    },
    "exhaustive": true
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "runnable",
    "kind": "inline_c_computation",
    "command": "cc -O3 -std=c11 -Wall -Wextra -pedantic search.c -o search && ./search",
    "runtime": "ISO C11; reproduced with Apple clang at -O3",
    "citation": {
      "url": "https://doi.org/10.1088/0951-7715/18/5/015",
      "locator": "Self-contained ISO C11 computation reproduced by TheoremDB entry research on 2026-07-25"
    },
    "inline_source": "#include <assert.h>\n#include <inttypes.h>\n#include <stdint.h>\n#include <stdio.h>\n\n#define P UINT64_C(1000003)\n#define SAMPLES UINT64_C(4096)\n\nstatic inline void step(uint64_t *x, uint64_t *y) {\n  uint64_t yy = (*y + (*x) * (*x)) % P;\n  *x = (*x + yy) % P;\n  *y = yy;\n}\n\nstatic uint64_t splitmix64(uint64_t *state) {\n  uint64_t z = (*state += UINT64_C(0x9e3779b97f4a7c15));\n  z = (z ^ (z >> 30)) * UINT64_C(0xbf58476d1ce4e5b9);\n  z = (z ^ (z >> 27)) * UINT64_C(0x94d049bb133111eb);\n  return z ^ (z >> 31);\n}\n\nstatic uint64_t period(uint64_t x0, uint64_t y0) {\n  uint64_t x = x0, y = y0, n = 0;\n  do {\n    step(&x, &y);\n    ++n;\n  } while (x != x0 || y != y0);\n  return n;\n}\n\nstatic void replay_witness(void) {\n  const uint64_t x0 = UINT64_C(343233);\n  const uint64_t y0 = UINT64_C(119429);\n  const uint64_t witness_period = UINT64_C(11656512);\n  const uint64_t checks[] = {\n      1, 2, 10, 100, 1000, 1000000, 5000000, 10000000,\n      witness_period - 1, witness_period};\n  uint64_t x = x0, y = y0;\n  uint64_t fnv = UINT64_C(14695981039346656037);\n  size_t ci = 0;\n  for (uint64_t i = 0; i < witness_period; ++i) {\n    uint64_t fields[] = {x, y};\n    for (unsigned k = 0; k < 2; ++k)\n      for (unsigned j = 0; j < 8; ++j) {\n        fnv ^= (uint8_t)(fields[k] >> (8 * j));\n        fnv *= UINT64_C(1099511628211);\n      }\n    step(&x, &y);\n    assert(i + 1 == witness_period || x != x0 || y != y0);\n    if (ci < sizeof(checks) / sizeof(checks[0]) && i + 1 == checks[ci]) {\n      fprintf(stderr, \"checkpoint=%\" PRIu64 \" x=%\" PRIu64 \" y=%\" PRIu64 \"\\n\",\n              i + 1, x, y);\n      ++ci;\n    }\n  }\n  assert(x == x0 && y == y0);\n  assert(fnv == UINT64_C(0xe1b26cc098a16596));\n  printf(\"witness p=%\" PRIu64 \" x=%\" PRIu64 \" y=%\" PRIu64\n         \" period=%\" PRIu64 \" trace_fnv1a=%016\" PRIx64 \"\\n\",\n         P, x0, y0, witness_period, fnv);\n}\n\nint main(void) {\n  uint64_t rng = UINT64_C(0x6b69636b65646d61);\n  uint64_t best = 0, best_i = 0, best_x = 0, best_y = 0;\n  uint64_t fnv = UINT64_C(14695981039346656037);\n  for (uint64_t d = 2; d * d <= P; ++d) assert(P % d != 0);\n  for (uint64_t i = 0; i < SAMPLES; ++i) {\n    uint64_t x = splitmix64(&rng) % P;\n    uint64_t y = splitmix64(&rng) % P;\n    uint64_t n = period(x, y);\n    uint64_t fields[] = {i, x, y, n};\n    for (unsigned k = 0; k < 4; ++k)\n      for (unsigned j = 0; j < 8; ++j) {\n        fnv ^= (uint8_t)(fields[k] >> (8 * j));\n        fnv *= UINT64_C(1099511628211);\n      }\n    if (n > best) {\n      best = n;\n      best_i = i;\n      best_x = x;\n      best_y = y;\n      printf(\"record i=%\" PRIu64 \" x=%\" PRIu64 \" y=%\" PRIu64\n             \" period=%\" PRIu64 \"\\n\", i, x, y, n);\n      fflush(stdout);\n    }\n  }\n  assert(best_i == 234 && best_x == 343233 && best_y == 119429);\n  assert(best == UINT64_C(11656512));\n  assert(fnv == UINT64_C(0xf6dd5727b5ac0b50));\n  printf(\"samples=%\" PRIu64 \" best_i=%\" PRIu64 \" best_x=%\" PRIu64\n         \" best_y=%\" PRIu64 \" best_period=%\" PRIu64\n         \" records_fnv1a=%016\" PRIx64 \"\\n\",\n         SAMPLES, best_i, best_x, best_y, best, fnv);\n  replay_witness();\n  return 0;\n}\n",
    "missing": [
      "expected_output"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://doi.org/10.1088/0951-7715/18/5/015",
    "locator": "Self-contained ISO C11 computation reproduced by TheoremDB entry research on 2026-07-25"
  },
  "relations": [
    {
      "slug": "R431",
      "title": "A certified cycle has length 11,656,512",
      "object_type": "claim",
      "relation": "verifies",
      "direction": "outgoing"
    },
    {
      "slug": "R429",
      "title": "Complete small-prime cycle decompositions",
      "object_type": "artifact",
      "relation": "tests",
      "direction": "incoming"
    },
    {
      "slug": "kicked-map-million-prime-cycle",
      "title": "kicked map million prime cycle",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}