{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R253",
  "content_hash": null,
  "slug": "ffe-artifact-primes-below-500",
  "type": "artifact",
  "title": "Executable Fibonacci-cycle exact-cover census",
  "summary": "Standard-library Python enumerates every pair orbit, filters eligible cycles, and counts every exact cover.",
  "relevance": "For Power-of-two solution counts for a finite-field functional equation, record ffe-artifact-primes-below-500 (“Executable Fibonacci-cycle exact-cover census”) supplies evidence or a replay used to check the packet. The record states: Standard-library Python enumerates every pair orbit, filters eligible cycles, and counts every exact cover.",
  "relevance_source": "recorded",
  "body": "Each pair \\((u,v)\\) is encoded by the integer \\(pu+v\\). A byte array marks all \\(p^2\\) states while the program follows the invertible map \\((u,v)\\mapsto(v,u+v)\\). Eligible projection sets are Python integer bit masks. The recursive counter selects an uncovered element with the fewest currently compatible cycles and sums over every such choice.\n\nThe code asserts the number of tested primes, the power-of-two property in the bounded range, and the complete count distribution. It prints selected counts and the digest of the full canonical record. The seven-line output has SHA-256 digest `01469652117bd7508b75c6764cbd07fe2a1a5d5a17e5b8a6376f14759946f1d5`.",
  "status": "available",
  "evidence_grade": "executable",
  "scope": {
    "kind": "bounded",
    "statement": "complete Fibonacci-map cycle enumeration and exact-cover counting for every prime below 500",
    "bounds": {
      "prime_upper_bound_exclusive": {
        "min": 500,
        "max": 500
      },
      "primes_checked": {
        "min": 95,
        "max": 95
      }
    },
    "exhaustive": true
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "partial",
    "kind": "inline_python_computation",
    "entrypoint": "join source_lines with newline and run with python3",
    "runtime": "CPython 3, standard library only",
    "citation": {
      "url": "https://sites.math.rutgers.edu/~nussbaum/Pubs/dynamicsJDE.pdf",
      "locator": "Inline CPython standard-library computation executed on 2026-07-24"
    },
    "inline_source": [
      "from collections import Counter",
      "from functools import lru_cache",
      "from hashlib import sha256",
      "def primes_below(limit):",
      "    sieve=bytearray(b'\\x01')*limit",
      "    sieve[:2]=b'\\x00\\x00'",
      "    for q in range(2,int((limit-1)**0.5)+1):",
      "        if sieve[q]:",
      "            sieve[q*q:limit:q]=b'\\x00'*(((limit-1-q*q)//q)+1)",
      "    return [q for q in range(2,limit) if sieve[q]]",
      "def solution_count(p):",
      "    seen=bytearray(p*p)",
      "    masks=[]",
      "    total_cycles=0",
      "    for code in range(p*p):",
      "        if seen[code]:",
      "            continue",
      "        total_cycles+=1",
      "        a,b=divmod(code,p)",
      "        first=[]",
      "        while not seen[a*p+b]:",
      "            seen[a*p+b]=1",
      "            first.append(a)",
      "            a,b=b,(a+b)%p",
      "        if 0 not in first and len(set(first))==len(first):",
      "            masks.append(sum(1<<x for x in first))",
      "    by_element=[[] for _ in range(p)]",
      "    for mask in masks:",
      "        remaining=mask",
      "        while remaining:",
      "            bit=remaining&-remaining",
      "            by_element[bit.bit_length()-1].append(mask)",
      "            remaining-=bit",
      "    full=((1<<p)-1)^1",
      "    @lru_cache(None)",
      "    def covers(remaining):",
      "        if not remaining:",
      "            return 1",
      "        scan=remaining",
      "        best=None",
      "        while scan:",
      "            bit=scan&-scan",
      "            element=bit.bit_length()-1",
      "            options=[mask for mask in by_element[element] if mask&remaining==mask]",
      "            if not options:",
      "                return 0",
      "            if best is None or len(options)<len(best):",
      "                best=options",
      "            scan-=bit",
      "        return sum(covers(remaining^mask) for mask in best)",
      "    count=covers(full)",
      "    return count,len(masks),total_cycles,covers.cache_info().currsize",
      "rows=[]",
      "for p in primes_below(500):",
      "    rows.append((p,)+solution_count(p))",
      "assert len(rows)==95",
      "assert all(n==0 or n&(n-1)==0 for p,n,e,t,c in rows)",
      "positive=[(p,n) for p,n,e,t,c in rows if n]",
      "distribution=Counter(n for p,n in positive)",
      "assert distribution==Counter({2:30,4:7,8:3,32:3,1:1,512:1,1024:1})",
      "record_raw=''.join(f'{p}:{n}:{e}:{t}:{c}\\n' for p,n,e,t,c in rows)",
      "digest=sha256(record_raw.encode()).hexdigest()",
      "assert digest=='c8ef45793aebcc55c45cb1ee99d55c67d9e418b867c5b5d6939f92e9493d2e37'",
      "selected={5,11,29,139,199,211,281,461}",
      "largest=max((n,p) for p,n in positive)",
      "print('primes_checked=95 range=2..499')",
      "print(f'positive_counts={len(positive)} zero_counts={95-len(positive)}')",
      "print(f'all_positive_powers_of_two={all(n&(n-1)==0 for p,n in positive)}')",
      "print('count_distribution='+','.join(f'{n}:{distribution[n]}' for n in sorted(distribution)))",
      "print('selected='+','.join(f'{p}:{n}' for p,n in positive if p in selected))",
      "print(f'maximum={largest[0]} at_p={largest[1]}')",
      "print(f'records_sha256={digest}')"
    ],
    "missing": [
      "command",
      "expected_output"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://sites.math.rutgers.edu/~nussbaum/Pubs/dynamicsJDE.pdf",
    "locator": "Inline CPython standard-library computation executed on 2026-07-24"
  },
  "relations": [
    {
      "slug": "R255",
      "title": "Exact orbit-cover counts for every prime below 500",
      "object_type": "claim",
      "relation": "verifies",
      "direction": "outgoing"
    },
    {
      "slug": "R258",
      "title": "The power-of-two claim is verified below 500 and unresolved in general",
      "object_type": "claim",
      "relation": "tests",
      "direction": "outgoing"
    },
    {
      "slug": "fibonacci-functional-equation-prime-count",
      "title": "fibonacci functional equation prime count",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}