{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R639",
  "content_hash": null,
  "slug": "r30n24-artifact-dual-exhaustive-scan",
  "type": "artifact",
  "title": "Dual exhaustive C11 verifier for cyclic Rule 30",
  "summary": "Path marking and indegree peeling independently scan the full graph, compare every cycle record, and check the known maxima through width 20.",
  "relevance": "This supplies a computation, dataset, or executable check used to assess the target problem.",
  "relevance_source": "derived",
  "body": "The path-marking scan and the indegree-peeling scan use separate state arrays and separate cycle-discovery logic. They evaluate the same explicit bitwise update, then compare all 49 sorted cycle records. The program also checks the maximum-cycle vector for widths 3 through 20 supplied with the candidate problem.\n\nIts complete six-line output is 493 bytes including the final newline and has SHA-256 digest `be6fc56a241c6a445ea9d4bec0945b0ea466ecd9ed766ae4f670f66b774038cc`.",
  "status": "available",
  "evidence_grade": "executable",
  "scope": {
    "kind": "bounded",
    "statement": "all states and directed cycles of cyclic Rule 30 on 24 binary cells",
    "bounds": {
      "ring_width": {
        "min": 24,
        "max": 24
      },
      "state": {
        "min": 0,
        "max": 16777215
      }
    },
    "exhaustive": true
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "runnable",
    "kind": "inline_c11_computation",
    "command": "cc -O3 -std=c11 -Wall -Wextra -pedantic check.c -o check && ./check",
    "entrypoint": "Join source_lines with newline, save as check.c, compile with the command in metadata.execution, and run",
    "runtime": "ISO C11",
    "citation": {
      "url": "https://oeis.org/A334497",
      "locator": "Inline ISO C11 source below, compiled and executed on 2026-07-24"
    },
    "inline_source": [
      "#include <inttypes.h>",
      "#include <stdint.h>",
      "#include <stdio.h>",
      "#include <stdlib.h>",
      "#include <string.h>",
      "",
      "typedef struct { uint32_t rep, len; } Cycle;",
      "typedef struct { Cycle *v; size_t n, cap; } CycleVec;",
      "typedef struct {",
      "    CycleVec cycles;",
      "    uint64_t cyclic_states;",
      "    uint32_t max_len, max_count, max_rep, fixed_points, max_indegree;",
      "} Result;",
      "",
      "static uint32_t rule30(uint32_t x, unsigned n) {",
      "    uint32_t mask = (UINT32_C(1) << n) - 1;",
      "    uint32_t left = (x >> 1) | ((x & 1u) << (n - 1));",
      "    uint32_t right = ((x << 1) & mask) | (x >> (n - 1));",
      "    return (left ^ (x | right)) & mask;",
      "}",
      "",
      "static void push(CycleVec *a, uint32_t rep, uint32_t len) {",
      "    if (a->n == a->cap) {",
      "        size_t cap = a->cap ? 2*a->cap : 256;",
      "        Cycle *v = realloc(a->v, cap * sizeof(*v));",
      "        if (!v) { perror(\"realloc\"); exit(2); }",
      "        a->v = v; a->cap = cap;",
      "    }",
      "    a->v[a->n++] = (Cycle){rep, len};",
      "}",
      "",
      "static int cycle_cmp(const void *pa, const void *pb) {",
      "    const Cycle *a = pa, *b = pb;",
      "    if (a->rep != b->rep) return a->rep < b->rep ? -1 : 1;",
      "    return a->len < b->len ? -1 : a->len > b->len;",
      "}",
      "",
      "static void finish(Result *r) {",
      "    qsort(r->cycles.v, r->cycles.n, sizeof(Cycle), cycle_cmp);",
      "    r->max_rep = UINT32_MAX;",
      "    for (size_t i=0; i<r->cycles.n; ++i) {",
      "        uint32_t len = r->cycles.v[i].len;",
      "        r->cyclic_states += len;",
      "        if (len == 1) ++r->fixed_points;",
      "        if (len > r->max_len) {",
      "            r->max_len = len; r->max_count = 1; r->max_rep = r->cycles.v[i].rep;",
      "        } else if (len == r->max_len) {",
      "            ++r->max_count;",
      "            if (r->cycles.v[i].rep < r->max_rep) r->max_rep = r->cycles.v[i].rep;",
      "        }",
      "    }",
      "}",
      "",
      "static Result path_scan(unsigned n) {",
      "    uint32_t count = UINT32_C(1) << n;",
      "    uint32_t *mark = calloc(count, sizeof(*mark));",
      "    if (!mark) { perror(\"calloc mark\"); exit(2); }",
      "    Result r = {0};",
      "    uint32_t run = 0;",
      "    for (uint32_t root=0; root<count; ++root) {",
      "        if (mark[root]) continue;",
      "        ++run;",
      "        uint32_t x = root;",
      "        while (!mark[x]) { mark[x] = run; x = rule30(x,n); }",
      "        if (mark[x] == run) {",
      "            uint32_t rep=x, len=1, y=rule30(x,n);",
      "            while (y != x) { if (y<rep) rep=y; ++len; y=rule30(y,n); }",
      "            push(&r.cycles, rep, len);",
      "        }",
      "        x = root;",
      "        while (mark[x] == run) {",
      "            mark[x] = UINT32_MAX;",
      "            x = rule30(x,n);",
      "        }",
      "    }",
      "    for (uint32_t x=0; x<count; ++x) if (mark[x] != UINT32_MAX) exit(3);",
      "    free(mark);",
      "    finish(&r);",
      "    return r;",
      "}",
      "",
      "static Result peel_scan(unsigned n) {",
      "    uint32_t count = UINT32_C(1) << n;",
      "    uint32_t *next = malloc((size_t)count * sizeof(*next));",
      "    uint8_t *indeg = calloc(count, sizeof(*indeg));",
      "    uint32_t *queue = malloc((size_t)count * sizeof(*queue));",
      "    if (!next || !indeg || !queue) { perror(\"peel allocation\"); exit(2); }",
      "    Result r = {0};",
      "    for (uint32_t x=0; x<count; ++x) {",
      "        uint32_t y = next[x] = rule30(x,n);",
      "        if (indeg[y] == UINT8_MAX) exit(4);",
      "        ++indeg[y];",
      "        if (indeg[y] > r.max_indegree) r.max_indegree = indeg[y];",
      "    }",
      "    uint32_t head=0, tail=0;",
      "    for (uint32_t x=0; x<count; ++x) if (!indeg[x]) queue[tail++]=x;",
      "    while (head<tail) {",
      "        uint32_t y=next[queue[head++]];",
      "        if (--indeg[y] == 0) queue[tail++]=y;",
      "    }",
      "    for (uint32_t x=0; x<count; ++x) if (indeg[x]) {",
      "        uint32_t y=x, rep=x, len=0;",
      "        do {",
      "            if (!indeg[y]) exit(5);",
      "            indeg[y]=0; if (y<rep) rep=y; ++len; y=next[y];",
      "        } while (y!=x);",
      "        push(&r.cycles,rep,len);",
      "    }",
      "    free(queue); free(indeg); free(next);",
      "    finish(&r);",
      "    if (r.cyclic_states != (uint64_t)count-tail) exit(6);",
      "    return r;",
      "}",
      "",
      "static uint64_t fnv_byte(uint64_t h, uint8_t x) {",
      "    return (h ^ x) * UINT64_C(1099511628211);",
      "}",
      "static uint64_t inventory_hash(const CycleVec *a) {",
      "    uint64_t h=UINT64_C(14695981039346656037);",
      "    for (size_t i=0; i<a->n; ++i) {",
      "        uint32_t words[2]={a->v[i].rep,a->v[i].len};",
      "        for (int w=0; w<2; ++w) for (int j=0; j<4; ++j)",
      "            h=fnv_byte(h,(uint8_t)(words[w]>>(8*j)));",
      "    }",
      "    return h;",
      "}",
      "static uint64_t orbit_hash(uint32_t rep, unsigned n, uint32_t expected) {",
      "    uint64_t h=UINT64_C(14695981039346656037);",
      "    uint32_t x=rep, len=0;",
      "    do {",
      "        for (int j=0;j<4;++j) h=fnv_byte(h,(uint8_t)(x>>(8*j)));",
      "        x=rule30(x,n); ++len;",
      "        if (len>expected) exit(7);",
      "    } while (x!=rep);",
      "    if (len!=expected) exit(8);",
      "    return h;",
      "}",
      "static void free_result(Result *r) { free(r->cycles.v); r->cycles.v=NULL; }",
      "",
      "int main(void) {",
      "    static const uint32_t expected[21] = {",
      "        0,0,0,1,8,5,1,63,40,171,15,154,102,832,1428,1455,6016,10846,2844,3705,6150",
      "    };",
      "    printf(\"small_width_maxima\");",
      "    for (unsigned n=3;n<=20;++n) {",
      "        Result r=path_scan(n);",
      "        if (r.max_len!=expected[n]) return 9;",
      "        printf(\" %u:%u\",n,r.max_len);",
      "        free_result(&r);",
      "    }",
      "    putchar('\\n');",
      "    Result a=path_scan(24), b=peel_scan(24);",
      "    if (a.cycles.n!=b.cycles.n || a.cyclic_states!=b.cyclic_states ||",
      "        a.max_len!=b.max_len || a.max_count!=b.max_count) return 10;",
      "    for (size_t i=0;i<a.cycles.n;++i)",
      "        if (a.cycles.v[i].rep!=b.cycles.v[i].rep || a.cycles.v[i].len!=b.cycles.v[i].len) return 11;",
      "    uint64_t hash=inventory_hash(&a.cycles);",
      "    if (hash!=inventory_hash(&b.cycles)) return 12;",
      "    uint64_t ohash=orbit_hash(a.max_rep,24,a.max_len);",
      "    printf(\"states 16777216 cycles %zu cyclic_states %\" PRIu64 \" fixed_points %u distinct_components %zu\\n\",",
      "           a.cycles.n,a.cyclic_states,a.fixed_points,a.cycles.n);",
      "    printf(\"maximum_cycle_length %u cycles_at_maximum %u witness_decimal %u witness_hex %06x\\n\",",
      "           a.max_len,a.max_count,a.max_rep,a.max_rep);",
      "    printf(\"cycle_inventory_fnv1a64 %016\" PRIx64 \" witness_orbit_fnv1a64 %016\" PRIx64 \"\\n\",hash,ohash);",
      "    printf(\"independent_algorithms_match 1 maximum_global_indegree %u\\n\",b.max_indegree);",
      "    printf(\"witness_bits_msb_to_lsb \");",
      "    for (int i=23;i>=0;--i) putchar('0'+((a.max_rep>>i)&1));",
      "    putchar('\\n');",
      "    free_result(&a); free_result(&b);",
      "    return 0;",
      "}"
    ],
    "missing": [
      "expected_output"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://oeis.org/A334497",
    "locator": "Inline ISO C11 source below, compiled and executed on 2026-07-24"
  },
  "models": [],
  "continuation": null,
  "relations": [
    {
      "slug": "R642",
      "title": "The maximum cycle length at width 24 is 185,040",
      "object_type": "claim",
      "relation": "evidences",
      "direction": "outgoing"
    },
    {
      "slug": "R641",
      "title": "The width-24 graph has 49 components and 194,991 cyclic states",
      "object_type": "claim",
      "relation": "evidences",
      "direction": "outgoing"
    },
    {
      "slug": "rule-30-cycle-length-24",
      "title": "rule 30 cycle length 24",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}