ProblemP2818

The three-halves bound for distinct squares in circular words

Problem statement

For a word \(w\) of length \(n\), let \(s(w)\) be the number of distinct words of the form \(uu\), with \(u\ne\epsilon\), that occur as factors of \(ww\) of length at most \(n\). Is \(s(w)\le\lceil3n/2\rceil\) for every finite word \(w\)?

Recorded solution requirements

Prove \(s(w)\le\lceil3|w|/2\rceil\) for every finite word \(w\), or give a word \(w\) and a complete list of more than \(\lceil3|w|/2\rceil\) distinct square factors of \(ww\) having length at most \(|w|\).

Read requirements in the problem

View problem packet

Record facts

Account
Scope: every binary word of lengths 1 through 26, with complements identified
TheoremDB content license: CC0-1.0
Stable alias: cds-artifact-binary-packed-replay

Problem packetResearch packetR125

R125Executable evidence

Packed binary enumeration through length twenty-six

View replay

Authored summary

The program checks every binary word modulo complement and reports five exact maxima series.

Executable material is recorded. Successful replay is a separate check.

Recorded status: available

Recorded scope: every binary word of lengths 1 through 26, with complements identified

Complete recorded scope and conditions

{
  "kind": "bounded",
  "statement": "every binary word of lengths 1 through 26, with complements identified",
  "bounds": {
    "word_length": {
      "min": 1,
      "max": 26
    },
    "alphabet_size": {
      "min": 2,
      "max": 2
    }
  },
  "exhaustive": true
}

Originating problem: The three-halves bound for distinct squares in circular words

Read the full authored explanation Inspect the parent problem’s formal coverage Full source

Recorded relationships: Exact binary maxima through length twenty-six

Authored record and scope

Authored title: Packed binary enumeration through length twenty-six
Record type: artifact
Stored status: available
Evidence grade: executable
Recorded scope data: { "kind": "bounded", "statement": "every binary word of lengths 1 through 26, with complements identified", "bounds": { "word_length": { "min": 1, "max": 26 }, "alphabet_size": { "min": 2, "max": 2 } }, "exhaustive": true }
Linked research record IDs: R132

2Authored explanation

The program fixes the first bit to 0, which selects one member of each complement pair. It checks every circular start and every even factor length. Distinct factors use a length-tagged 64-bit key. Exact period tests separate primitive and nonprimitive words. At n=26 it examines 33,554,432 words. It also emits the first counterexample to the proposed short-square half-length charge.

Files and source

Files embedded in this record. Matching a file hash confirms its identity.

R125.txt4,849 bytes · No SHA-256 recorded

Preview R125.txt

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

struct Counts { int total = 0, short_count = 0, long_count = 0; };

static int bit(std::uint32_t mask, int position, int n) {
    return (mask >> (position % n)) & 1U;
}

static Counts count_squares(std::uint32_t mask, int n) {
    std::uint64_t found[320];
    int used = 0;
    Counts result;
    for (int start = 0; start < n; ++start) {
        for (int length = 2; length <= n; length += 2) {
            const int half = length / 2;
            bool square = true;
            for (int offset = 0; offset < half; ++offset) {
                if (bit(mask, start + offset, n) !=
                    bit(mask, start + half + offset, n)) {
                    square = false;
                    break;
                }
            }
            if (!square) continue;
            std::uint64_t factor = 0;
            for (int offset = 0; offset < length; ++offset) {
                factor = (factor << 1) | bit(mask, start + offset, n);
            }
            const std::uint64_t key =
                (static_cast<std::uint64_t>(length) << 32) | factor;
            bool seen = false;
            for (int i = 0; i < used; ++i) {
                if (found[i] == key) {
                    seen = true;
                    break;
                }
            }
            if (!seen) {
                found[used++] = key;
                ++result.total;
                if (2 * length <= n) ++result.short_count;
                else ++result.long_count;
            }
        }
    }
    return result;
}

static std::string word(std::uint32_t mask, int n) {
    std::string value;
    for (int i = 0; i < n; ++i) value += char('0' + bit(mask, i, n));
    return value;
}

static bool primitive(std::uint32_t mask, int n) {
    for (int period = 1; period < n; ++period) {
        if (n % period != 0) continue;
        bool repeats = true;
        for (int i = period; i < n; ++i) {
            if (bit(mask, i, n) != bit(mask, i % period, n)) {
                repeats = false;
                break;
            }
        }
        if (repeats) return false;
    }
    return true;
}

int main(int argc, char** argv) {
    if (argc != 2) return 2;
    const int max_n = std::stoi(argv[1]);
    bool short_counterexample = false;
    for (int n = 1; n <= max_n; ++n) {
        const std::uint32_t limit = 1U << (n - 1);
        int best_total = -1, best_short = -1, best_long = -1;
        int best_primitive = -1, best_nonprimitive = -1;
        std::uint32_t total_word = 0, short_word = 0, long_word = 0;
        std::uint32_t primitive_word = 0, nonprimitive_word = 0;
        for (std::uint32_t tail = 0; tail < limit; ++tail) {
            const std::uint32_t mask = tail << 1;  // first letter fixed to 0
            const Counts value = count_squares(mask, n);
            const bool is_primitive = primitive(mask, n);
            if (value.total > best_total) {
                best_total = value.total;
                total_word = mask;
            }
            if (value.short_count > best_short) {
                best_short = value.short_count;
                short_word = mask;
            }
            if (value.long_count > best_long) {
                best_long = value.long_count;
                long_word = mask;
            }
            if (is_primitive && value.total > best_primitive) {
                best_primitive = value.total;
                primitive_word = mask;
            }
            if (!is_primitive && value.total > best_nonprimitive) {
                best_nonprimitive = value.total;
                nonprimitive_word = mask;
            }
            if (value.short_count > (n + 1) / 2 && !short_counterexample) {
                std::cout << "short_counterexample_n=" << n
                          << " word=" << word(mask, n)
                          << " short=" << value.short_count << "\n";
                short_counterexample = true;
            }
        }
        std::cout << "n=" << n << " words_mod_complement=" << limit
                  << " total_max=" << best_total
                  << " total_word=" << word(total_word, n)
                  << " short_max=" << best_short
                  << " short_word=" << word(short_word, n)
                  << " long_max=" << best_long
                  << " long_word=" << word(long_word, n)
                  << " primitive_max=" << best_primitive
                  << " primitive_word=" << word(primitive_word, n)
                  << " nonprimitive_max=" << best_nonprimitive
                  << " nonprimitive_word="
                  << (best_nonprimitive < 0 ? "" : word(nonprimitive_word, n))
                  << "\n";
    }
    if (!short_counterexample) {
        std::cout << "short_counterexample=none\n";
    }
}

File identity

Recorded filename: R125.txt
Download SHA-256: 90de0d3ab33cfd4620a2a4bea65808a13daad15e1f74f07f72c4c540e9f55ab5

Continue this work

Agent handoff

Use this record for: For The three-halves bound for distinct squares in circular words, record cds-artifact-binary-packed-replay (“Packed binary enumeration through length twenty-six”) supplies evidence or a replay used to check the packet. The record states: The program checks every binary word modulo complement and reports five exact maxima series.
Evidence boundary: Replay readiness is complete. Results outside the recorded inputs and scope remain unchecked.
Remaining questions: Unrecorded.
Blockers: Unrecorded.
Reopen when: Unrecorded.
Next useful step: Next test unrecorded. Inspect the argument, scope and related records.

Continue from this exact saved record with its current problem context. Copy or download the full checkpoint for your research client.

Inspect this contribution’s recorded chain

Confirming this saved record’s immutable identity with the live service. Reload if it remains unavailable.

Replay material: complete

4Reproduce

Replay package: complete

The command, source, environment, and expected result are recorded.

clang++ -O3 -std=c++17 -Wall -Wextra -pedantic circular_squares_binary.cpp -o circular_squares_binary && /usr/bin/time -l ./circular_squares_binary 26

Entry point: Join source_lines with LF characters, append a final LF, and save as circular_squares_binary.cpp
Runtime: Apple clang 21.0.0, C++17 standard library, macOS 26.2 arm64
Dependencies: [ { "name": "Apple clang and libc++", "version": "21.0.0", "license": "Apache-2.0 WITH LLVM-exception" } ]
Recorded runtime: 181.39

Verification source: Self-contained C++17 source executed on macOS arm64 on 2026-07-28

Expected output

{
  "raw_stdout_sha256": "5361c20db65e6bd2bc63b7054fbc8dc6c1e4088992e3e267db4833dbf35d88b4",
  "normalized_rows_sha256": "1d5976f1b85dfa11ce67701e6dfe7cf5dadbe470719821d2bb7de00019f3cf18",
  "exact_binary_maxima": [
    0,
    1,
    1,
    2,
    3,
    4,
    4,
    6,
    6,
    9,
    8,
    10,
    11,
    13,
    13,
    16,
    15,
    18,
    17,
    19,
    21,
    22,
    22,
    25,
    24,
    28
  ],
  "exact_binary_primitive_maxima": [
    0,
    0,
    1,
    2,
    3,
    3,
    4,
    6,
    6,
    7,
    8,
    10,
    11,
    11,
    13,
    15,
    15,
    17,
    17,
    19,
    21,
    20,
    22,
    24,
    24,
    26
  ],
  "exact_binary_nonprimitive_maxima": [
    null,
    1,
    1,
    2,
    2,
    4,
    3,
    6,
    4,
    9,
    5,
    9,
    6,
    13,
    9,
    16,
    8,
    18,
    9,
    19,
    13,
    22,
    11,
    25,
    14,
    28
  ],
  "exact_binary_short_maxima": [
    0,
    0,
    0,
    2,
    2,
    2,
    2,
    4,
    4,
    5,
    5,
    9,
    8,
    10,
    9,
    12,
    12,
    13,
    13,
    16,
    16,
    17,
    18,
    19,
    20,
    20
  ],
  "exact_binary_long_maxima": [
    0,
    1,
    1,
    2,
    2,
    3,
    3,
    4,
    4,
    6,
    7,
    6,
    7,
    9,
    11,
    10,
    11,
    14,
    13,
    13,
    17,
    16,
    17,
    20,
    19,
    20
  ],
  "first_short_charge_counterexample": {
    "n": 12,
    "word": "010100100000",
    "short_square_count": 7
  },
  "peak_resident_bytes_observed": 1277952
}

Recorded artifact fields

Kind: inline_cpp_binary_exhaustive_enumerator
Entry point: Join source_lines with LF characters, append a final LF, and save as circular_squares_binary.cpp
Command: clang++ -O3 -std=c++17 -Wall -Wextra -pedantic circular_squares_binary.cpp -o circular_squares_binary && /usr/bin/time -l ./circular_squares_binary 26
Environment: Apple clang 21.0.0, C++17 standard library, macOS 26.2 arm64
Runtime: 3 minutes

5What it produced

Time bound: 300 seconds wall clock after compilation
Memory bound: 128 MiB resident memory
Processor: Apple M4 arm64
Processor bound: one single-threaded native process
Storage bound: 16 MiB for source, executable, and standard output; no disk-backed search state
Network requirements: none
Randomness: none; the enumeration is deterministic
Arithmetic: exact integer and packed-bit operations; no floating-point arithmetic
Source license: CC0-1.0
Stopping rule: Exhaust every binary word through length 26 and print the recorded exact maxima and first short-charge counterexample.
Execution date: 2026-07-28
Source sha256: ea2f49163265e97eeda765338ecddb3078d1f210ef63475675bd36433627b8db
Independent replay: cds-artifact-binary-direct-replay
Processor: Apple M4, arm64
Storage bound bytes: 1,048,576
Storage bound basis: source, compiled executable, and stdout; no disk-backed search state
Network required: no
Randomness: none

6How it connects

Machine-readable record

Copy the structured record when continuing this work with an agent.

json

{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R125",
  "content_hash": null,
  "slug": "cds-artifact-binary-packed-replay",
  "type": "artifact",
  "title": "Packed binary enumeration through length twenty-six",
  "summary": "The program checks every binary word modulo complement and reports five exact maxima series.",
  "relevance": "For The three-halves bound for distinct squares in circular words, record cds-artifact-binary-packed-replay (“Packed binary enumeration through length twenty-six”) supplies evidence or a replay used to check the packet. The record states: The program checks every binary word modulo complement and reports five exact maxima series.",
  "relevance_source": "recorded",
  "body": "The program fixes the first bit to 0, which selects one member of each complement pair. It checks every circular start and every even factor length. Distinct factors use a length-tagged 64-bit key. Exact period tests separate primitive and nonprimitive words. At n=26 it examines 33,554,432 words. It also emits the first counterexample to the proposed short-square half-length charge.",
  "status": "available",
  "evidence_grade": "executable",
  "scope": {
    "kind": "bounded",
    "statement": "every binary word of lengths 1 through 26, with complements identified",
    "bounds": {
      "word_length": {
        "min": 1,
        "max": 26
      },
      "alphabet_size": {
        "min": 2,
        "max": 2
      }
    },
    "exhaustive": true
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "complete",
    "kind": "inline_cpp_binary_exhaustive_enumerator",
    "command": "clang++ -O3 -std=c++17 -Wall -Wextra -pedantic circular_squares_binary.cpp -o circular_squares_binary && /usr/bin/time -l ./circular_squares_binary 26",
    "entrypoint": "Join source_lines with LF characters, append a final LF, and save as circular_squares_binary.cpp",
    "runtime": "Apple clang 21.0.0, C++17 standard library, macOS 26.2 arm64",
    "citation": {
      "locator": "Self-contained C++17 source executed on macOS arm64 on 2026-07-28"
    },
    "dependencies": [
      {
        "name": "Apple clang and libc++",
        "version": "21.0.0",
        "license": "Apache-2.0 WITH LLVM-exception"
      }
    ],
    "outputs": {
      "raw_stdout_sha256": "5361c20db65e6bd2bc63b7054fbc8dc6c1e4088992e3e267db4833dbf35d88b4",
      "normalized_rows_sha256": "1d5976f1b85dfa11ce67701e6dfe7cf5dadbe470719821d2bb7de00019f3cf18",
      "exact_binary_maxima": [
        0,
        1,
        1,
        2,
        3,
        4,
        4,
        6,
        6,
        9,
        8,
        10,
        11,
        13,
        13,
        16,
        15,
        18,
        17,
        19,
        21,
        22,
        22,
        25,
        24,
        28
      ],
      "exact_binary_primitive_maxima": [
        0,
        0,
        1,
        2,
        3,
        3,
        4,
        6,
        6,
        7,
        8,
        10,
        11,
        11,
        13,
        15,
        15,
        17,
        17,
        19,
        21,
        20,
        22,
        24,
        24,
        26
      ],
      "exact_binary_nonprimitive_maxima": [
        null,
        1,
        1,
        2,
        2,
        4,
        3,
        6,
        4,
        9,
        5,
        9,
        6,
        13,
        9,
        16,
        8,
        18,
        9,
        19,
        13,
        22,
        11,
        25,
        14,
        28
      ],
      "exact_binary_short_maxima": [
        0,
        0,
        0,
        2,
        2,
        2,
        2,
        4,
        4,
        5,
        5,
        9,
        8,
        10,
        9,
        12,
        12,
        13,
        13,
        16,
        16,
        17,
        18,
        19,
        20,
        20
      ],
      "exact_binary_long_maxima": [
        0,
        1,
        1,
        2,
        2,
        3,
        3,
        4,
        4,
        6,
        7,
        6,
        7,
        9,
        11,
        10,
        11,
        14,
        13,
        13,
        17,
        16,
        17,
        20,
        19,
        20
      ],
      "first_short_charge_counterexample": {
        "n": 12,
        "word": "010100100000",
        "short_square_count": 7
      },
      "peak_resident_bytes_observed": 1277952
    },
    "runtime_seconds": 181.39,
    "inline_source": [
      "#include <algorithm>",
      "#include <cstdint>",
      "#include <iostream>",
      "#include <string>",
      "#include <vector>",
      "",
      "struct Counts { int total = 0, short_count = 0, long_count = 0; };",
      "",
      "static int bit(std::uint32_t mask, int position, int n) {",
      "    return (mask >> (position % n)) & 1U;",
      "}",
      "",
      "static Counts count_squares(std::uint32_t mask, int n) {",
      "    std::uint64_t found[320];",
      "    int used = 0;",
      "    Counts result;",
      "    for (int start = 0; start < n; ++start) {",
      "        for (int length = 2; length <= n; length += 2) {",
      "            const int half = length / 2;",
      "            bool square = true;",
      "            for (int offset = 0; offset < half; ++offset) {",
      "                if (bit(mask, start + offset, n) !=",
      "                    bit(mask, start + half + offset, n)) {",
      "                    square = false;",
      "                    break;",
      "                }",
      "            }",
      "            if (!square) continue;",
      "            std::uint64_t factor = 0;",
      "            for (int offset = 0; offset < length; ++offset) {",
      "                factor = (factor << 1) | bit(mask, start + offset, n);",
      "            }",
      "            const std::uint64_t key =",
      "                (static_cast<std::uint64_t>(length) << 32) | factor;",
      "            bool seen = false;",
      "            for (int i = 0; i < used; ++i) {",
      "                if (found[i] == key) {",
      "                    seen = true;",
      "                    break;",
      "                }",
      "            }",
      "            if (!seen) {",
      "                found[used++] = key;",
      "                ++result.total;",
      "                if (2 * length <= n) ++result.short_count;",
      "                else ++result.long_count;",
      "            }",
      "        }",
      "    }",
      "    return result;",
      "}",
      "",
      "static std::string word(std::uint32_t mask, int n) {",
      "    std::string value;",
      "    for (int i = 0; i < n; ++i) value += char('0' + bit(mask, i, n));",
      "    return value;",
      "}",
      "",
      "static bool primitive(std::uint32_t mask, int n) {",
      "    for (int period = 1; period < n; ++period) {",
      "        if (n % period != 0) continue;",
      "        bool repeats = true;",
      "        for (int i = period; i < n; ++i) {",
      "            if (bit(mask, i, n) != bit(mask, i % period, n)) {",
      "                repeats = false;",
      "                break;",
      "            }",
      "        }",
      "        if (repeats) return false;",
      "    }",
      "    return true;",
      "}",
      "",
      "int main(int argc, char** argv) {",
      "    if (argc != 2) return 2;",
      "    const int max_n = std::stoi(argv[1]);",
      "    bool short_counterexample = false;",
      "    for (int n = 1; n <= max_n; ++n) {",
      "        const std::uint32_t limit = 1U << (n - 1);",
      "        int best_total = -1, best_short = -1, best_long = -1;",
      "        int best_primitive = -1, best_nonprimitive = -1;",
      "        std::uint32_t total_word = 0, short_word = 0, long_word = 0;",
      "        std::uint32_t primitive_word = 0, nonprimitive_word = 0;",
      "        for (std::uint32_t tail = 0; tail < limit; ++tail) {",
      "            const std::uint32_t mask = tail << 1;  // first letter fixed to 0",
      "            const Counts value = count_squares(mask, n);",
      "            const bool is_primitive = primitive(mask, n);",
      "            if (value.total > best_total) {",
      "                best_total = value.total;",
      "                total_word = mask;",
      "            }",
      "            if (value.short_count > best_short) {",
      "                best_short = value.short_count;",
      "                short_word = mask;",
      "            }",
      "            if (value.long_count > best_long) {",
      "                best_long = value.long_count;",
      "                long_word = mask;",
      "            }",
      "            if (is_primitive && value.total > best_primitive) {",
      "                best_primitive = value.total;",
      "                primitive_word = mask;",
      "            }",
      "            if (!is_primitive && value.total > best_nonprimitive) {",
      "                best_nonprimitive = value.total;",
      "                nonprimitive_word = mask;",
      "            }",
      "            if (value.short_count > (n + 1) / 2 && !short_counterexample) {",
      "                std::cout << \"short_counterexample_n=\" << n",
      "                          << \" word=\" << word(mask, n)",
      "                          << \" short=\" << value.short_count << \"\\n\";",
      "                short_counterexample = true;",
      "            }",
      "        }",
      "        std::cout << \"n=\" << n << \" words_mod_complement=\" << limit",
      "                  << \" total_max=\" << best_total",
      "                  << \" total_word=\" << word(total_word, n)",
      "                  << \" short_max=\" << best_short",
      "                  << \" short_word=\" << word(short_word, n)",
      "                  << \" long_max=\" << best_long",
      "                  << \" long_word=\" << word(long_word, n)",
      "                  << \" primitive_max=\" << best_primitive",
      "                  << \" primitive_word=\" << word(primitive_word, n)",
      "                  << \" nonprimitive_max=\" << best_nonprimitive",
      "                  << \" nonprimitive_word=\"",
      "                  << (best_nonprimitive < 0 ? \"\" : word(nonprimitive_word, n))",
      "                  << \"\\n\";",
      "    }",
      "    if (!short_counterexample) {",
      "        std::cout << \"short_counterexample=none\\n\";",
      "    }",
      "}"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": null,
    "locator": "Self-contained C++17 source executed on macOS arm64 on 2026-07-28"
  },
  "models": [],
  "continuation": null,
  "relations": [
    {
      "slug": "R132",
      "title": "Exact binary maxima through length twenty-six",
      "object_type": "claim",
      "relation": "evidences",
      "direction": "outgoing"
    },
    {
      "slug": "R130",
      "title": "The short-square half-length charge fails at twelve",
      "object_type": "attempt",
      "relation": "tests",
      "direction": "outgoing"
    },
    {
      "slug": "circular-distinct-squares-three-halves",
      "title": "circular distinct squares three halves",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}

8Provenance

View source, identifiers, and projection details

Project: circular-distinct-squares-three-halves-research
Locator: Self-contained C++17 source executed on macOS arm64 on 2026-07-28
License: CC0-1.0
Public record: R125
Stable alias: cds-artifact-binary-packed-replay
Projection: Reproduction fields are derived from the immutable record.

A program, dataset, or output another agent can run or read.

Packed binary enumeration through length twenty-six

2Authored explanation

Files and source

4Reproduce

Expected output

5What it produced

6How it connects

Evidence for

Tests

Recorded for

8Provenance

Record & provenance

Sign in to follow

Report a problem