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 finite word of lengths 1 through 14, modulo global alphabet renaming
TheoremDB content license: CC0-1.0
Stable alias: cds-artifact-rgs-direct-replay

Problem packetResearch packetR126

R126Executable evidence

Direct-factor independent restricted-growth replay

View replay

Authored summary

An independent C++17 implementation matches every total, primitive, and nonprimitive maximum through length 14.

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

Recorded status: available

Recorded scope: every finite word of lengths 1 through 14, modulo global alphabet renaming

Complete recorded scope and conditions

{
  "kind": "bounded",
  "statement": "every finite word of lengths 1 through 14, modulo global alphabet renaming",
  "bounds": {
    "word_length": {
      "min": 1,
      "max": 14
    },
    "alphabet_size": {
      "min": 1,
      "max": 14
    }
  },
  "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 maxima for every alphabet through length fourteen

Authored record and scope

Authored title: Direct-factor independent restricted-growth replay
Record type: artifact
Stored status: available
Evidence grade: executable
Recorded scope data: { "kind": "bounded", "statement": "every finite word of lengths 1 through 14, modulo global alphabet renaming", "bounds": { "word_length": { "min": 1, "max": 14 }, "alphabet_size": { "min": 1, "max": 14 } }, "exhaustive": true }
Linked research record IDs: R133

2Authored explanation

This replay generates the same complete restricted-growth space, then stores square factors by start and length and checks duplicates through direct character comparison. It shares no packed-factor representation with the first program. After field-name normalization, the two 14-line outputs have the same SHA-256 digest.

Files and source

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

R126.txt4,498 bytes · No SHA-256 recorded

Preview R126.txt

#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

static int count_distinct_squares(const std::vector<unsigned char>& word) {
    const int n = static_cast<int>(word.size());
    std::vector<unsigned char> circle(word);
    circle.insert(circle.end(), word.begin(), word.end());
    std::vector<std::pair<int, int>> distinct;
    for (int start = 0; start < n; ++start) {
        for (int length = 2; length <= n; length += 2) {
            const int half = length / 2;
            bool is_square = true;
            for (int offset = 0; offset < half; ++offset) {
                if (circle[start + offset] != circle[start + half + offset]) {
                    is_square = false;
                    break;
                }
            }
            if (!is_square) continue;
            bool seen = false;
            for (auto [old_start, old_length] : distinct) {
                if (old_length != length) continue;
                bool equal = true;
                for (int offset = 0; offset < length; ++offset) {
                    if (circle[start + offset] != circle[old_start + offset]) {
                        equal = false;
                        break;
                    }
                }
                if (equal) {
                    seen = true;
                    break;
                }
            }
            if (!seen) distinct.emplace_back(start, length);
        }
    }
    return static_cast<int>(distinct.size());
}

struct Summary {
    unsigned long long restricted_growth_strings = 0;
    unsigned long long maximizing_strings = 0;
    int maximum = -1;
    std::vector<unsigned char> first;
    int primitive_maximum = -1;
    std::vector<unsigned char> primitive_first;
    int nonprimitive_maximum = -1;
    std::vector<unsigned char> nonprimitive_first;
};

static bool primitive(const std::vector<unsigned char>& word) {
    const int n = static_cast<int>(word.size());
    for (int period = 1; period < n; ++period) {
        if (n % period) continue;
        bool repeats = true;
        for (int i = period; i < n; ++i) {
            if (word[i] != word[i % period]) {
                repeats = false;
                break;
            }
        }
        if (repeats) return false;
    }
    return true;
}

static void enumerate(std::vector<unsigned char>& word, int index,
                      unsigned char largest, Summary& summary) {
    if (index == static_cast<int>(word.size())) {
        ++summary.restricted_growth_strings;
        const int value = count_distinct_squares(word);
        if (value > summary.maximum) {
            summary.maximum = value;
            summary.maximizing_strings = 1;
            summary.first = word;
        } else if (value == summary.maximum) {
            ++summary.maximizing_strings;
        }
        if (primitive(word) && value > summary.primitive_maximum) {
            summary.primitive_maximum = value;
            summary.primitive_first = word;
        }
        if (!primitive(word) && value > summary.nonprimitive_maximum) {
            summary.nonprimitive_maximum = value;
            summary.nonprimitive_first = word;
        }
        return;
    }
    for (unsigned char letter = 0; letter <= largest + 1; ++letter) {
        word[index] = letter;
        enumerate(word, index + 1, std::max(largest, letter), summary);
    }
}

static std::string text(const std::vector<unsigned char>& word) {
    std::ostringstream out;
    for (unsigned char letter : word) out << static_cast<int>(letter);
    return out.str();
}

int main(int argc, char** argv) {
    if (argc != 2) return 2;
    const int maximum_length = std::stoi(argv[1]);
    for (int n = 1; n <= maximum_length; ++n) {
        Summary summary;
        std::vector<unsigned char> word(n, 0);
        enumerate(word, 1, 0, summary);
        std::cout << "length=" << n
                  << " rgs=" << summary.restricted_growth_strings
                  << " maximum=" << summary.maximum
                  << " maximizing_rgs=" << summary.maximizing_strings
                  << " first=" << text(summary.first)
                  << " primitive_maximum=" << summary.primitive_maximum
                  << " primitive_first=" << text(summary.primitive_first)
                  << " nonprimitive_maximum=" << summary.nonprimitive_maximum
                  << " nonprimitive_first=" << text(summary.nonprimitive_first)
                  << "\n";
    }
}

File identity

Recorded filename: R126.txt
Download SHA-256: 01270ed1e42801d12e1d8fff1daaf296e1db972d407c7eeb67157e48e51807c5

Continue this work

Agent handoff

Use this record for: For The three-halves bound for distinct squares in circular words, record cds-artifact-rgs-direct-replay (“Direct-factor independent restricted-growth replay”) supplies evidence or a replay used to check the packet. The record states: An independent C++17 implementation matches every total, primitive, and nonprimitive maximum through length 14.
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_replay_direct.cpp -o circular_squares_replay_direct && /usr/bin/time -l ./circular_squares_replay_direct 14

Entry point: Join source_lines with LF characters, append a final LF, and save as circular_squares_replay_direct.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: 62.73

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

Expected output

{
  "raw_stdout_sha256": "05522d1ef84a3ea39ee9160a4fca1717d1e1a494c2d8b99eaf5f786603f7f717",
  "normalized_stdout_sha256": "05522d1ef84a3ea39ee9160a4fca1717d1e1a494c2d8b99eaf5f786603f7f717",
  "exact_maxima": [
    0,
    1,
    1,
    2,
    3,
    4,
    4,
    6,
    6,
    9,
    8,
    10,
    11,
    13
  ],
  "primitive_maxima": [
    0,
    0,
    1,
    2,
    3,
    3,
    4,
    6,
    6,
    7,
    8,
    10,
    11,
    11
  ],
  "nonprimitive_maxima": [
    null,
    1,
    1,
    2,
    2,
    4,
    3,
    6,
    4,
    9,
    5,
    9,
    6,
    13
  ],
  "restricted_growth_counts": [
    1,
    2,
    5,
    15,
    52,
    203,
    877,
    4140,
    21147,
    115975,
    678570,
    4213597,
    27644437,
    190899322
  ],
  "peak_resident_bytes_observed": 1359872
}

Recorded artifact fields

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

5What it produced

Time bound: 120 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 direct string-factor operations; no floating-point arithmetic
Source license: CC0-1.0
Stopping rule: Exhaust every restricted-growth word through length 14 with the independent direct-factor counter.
Execution date: 2026-07-28
Source sha256: 77f65e7f2314cacb280ca1e33a88ddee4a80a25baf4f6f07f567162e8dd68302
Replay of: cds-artifact-rgs-packed-replay
Exact comparisons: yes
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

Evidence for

R126evidencesExact maxima for every alphabet through length fourteen
claim

Recorded for

R126recorded forcircular distinct squares three halves
problem

Machine-readable record

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

json

{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R126",
  "content_hash": null,
  "slug": "cds-artifact-rgs-direct-replay",
  "type": "artifact",
  "title": "Direct-factor independent restricted-growth replay",
  "summary": "An independent C++17 implementation matches every total, primitive, and nonprimitive maximum through length 14.",
  "relevance": "For The three-halves bound for distinct squares in circular words, record cds-artifact-rgs-direct-replay (“Direct-factor independent restricted-growth replay”) supplies evidence or a replay used to check the packet. The record states: An independent C++17 implementation matches every total, primitive, and nonprimitive maximum through length 14.",
  "relevance_source": "recorded",
  "body": "This replay generates the same complete restricted-growth space, then stores square factors by start and length and checks duplicates through direct character comparison. It shares no packed-factor representation with the first program. After field-name normalization, the two 14-line outputs have the same SHA-256 digest.",
  "status": "available",
  "evidence_grade": "executable",
  "scope": {
    "kind": "bounded",
    "statement": "every finite word of lengths 1 through 14, modulo global alphabet renaming",
    "bounds": {
      "word_length": {
        "min": 1,
        "max": 14
      },
      "alphabet_size": {
        "min": 1,
        "max": 14
      }
    },
    "exhaustive": true
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "complete",
    "kind": "inline_cpp_independent_exhaustive_enumerator",
    "command": "clang++ -O3 -std=c++17 -Wall -Wextra -pedantic circular_squares_replay_direct.cpp -o circular_squares_replay_direct && /usr/bin/time -l ./circular_squares_replay_direct 14",
    "entrypoint": "Join source_lines with LF characters, append a final LF, and save as circular_squares_replay_direct.cpp",
    "runtime": "Apple clang 21.0.0, C++17 standard library, macOS 26.2 arm64",
    "citation": {
      "locator": "Independent 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": "05522d1ef84a3ea39ee9160a4fca1717d1e1a494c2d8b99eaf5f786603f7f717",
      "normalized_stdout_sha256": "05522d1ef84a3ea39ee9160a4fca1717d1e1a494c2d8b99eaf5f786603f7f717",
      "exact_maxima": [
        0,
        1,
        1,
        2,
        3,
        4,
        4,
        6,
        6,
        9,
        8,
        10,
        11,
        13
      ],
      "primitive_maxima": [
        0,
        0,
        1,
        2,
        3,
        3,
        4,
        6,
        6,
        7,
        8,
        10,
        11,
        11
      ],
      "nonprimitive_maxima": [
        null,
        1,
        1,
        2,
        2,
        4,
        3,
        6,
        4,
        9,
        5,
        9,
        6,
        13
      ],
      "restricted_growth_counts": [
        1,
        2,
        5,
        15,
        52,
        203,
        877,
        4140,
        21147,
        115975,
        678570,
        4213597,
        27644437,
        190899322
      ],
      "peak_resident_bytes_observed": 1359872
    },
    "runtime_seconds": 62.73,
    "inline_source": [
      "#include <algorithm>",
      "#include <iostream>",
      "#include <sstream>",
      "#include <string>",
      "#include <utility>",
      "#include <vector>",
      "",
      "static int count_distinct_squares(const std::vector<unsigned char>& word) {",
      "    const int n = static_cast<int>(word.size());",
      "    std::vector<unsigned char> circle(word);",
      "    circle.insert(circle.end(), word.begin(), word.end());",
      "    std::vector<std::pair<int, int>> distinct;",
      "    for (int start = 0; start < n; ++start) {",
      "        for (int length = 2; length <= n; length += 2) {",
      "            const int half = length / 2;",
      "            bool is_square = true;",
      "            for (int offset = 0; offset < half; ++offset) {",
      "                if (circle[start + offset] != circle[start + half + offset]) {",
      "                    is_square = false;",
      "                    break;",
      "                }",
      "            }",
      "            if (!is_square) continue;",
      "            bool seen = false;",
      "            for (auto [old_start, old_length] : distinct) {",
      "                if (old_length != length) continue;",
      "                bool equal = true;",
      "                for (int offset = 0; offset < length; ++offset) {",
      "                    if (circle[start + offset] != circle[old_start + offset]) {",
      "                        equal = false;",
      "                        break;",
      "                    }",
      "                }",
      "                if (equal) {",
      "                    seen = true;",
      "                    break;",
      "                }",
      "            }",
      "            if (!seen) distinct.emplace_back(start, length);",
      "        }",
      "    }",
      "    return static_cast<int>(distinct.size());",
      "}",
      "",
      "struct Summary {",
      "    unsigned long long restricted_growth_strings = 0;",
      "    unsigned long long maximizing_strings = 0;",
      "    int maximum = -1;",
      "    std::vector<unsigned char> first;",
      "    int primitive_maximum = -1;",
      "    std::vector<unsigned char> primitive_first;",
      "    int nonprimitive_maximum = -1;",
      "    std::vector<unsigned char> nonprimitive_first;",
      "};",
      "",
      "static bool primitive(const std::vector<unsigned char>& word) {",
      "    const int n = static_cast<int>(word.size());",
      "    for (int period = 1; period < n; ++period) {",
      "        if (n % period) continue;",
      "        bool repeats = true;",
      "        for (int i = period; i < n; ++i) {",
      "            if (word[i] != word[i % period]) {",
      "                repeats = false;",
      "                break;",
      "            }",
      "        }",
      "        if (repeats) return false;",
      "    }",
      "    return true;",
      "}",
      "",
      "static void enumerate(std::vector<unsigned char>& word, int index,",
      "                      unsigned char largest, Summary& summary) {",
      "    if (index == static_cast<int>(word.size())) {",
      "        ++summary.restricted_growth_strings;",
      "        const int value = count_distinct_squares(word);",
      "        if (value > summary.maximum) {",
      "            summary.maximum = value;",
      "            summary.maximizing_strings = 1;",
      "            summary.first = word;",
      "        } else if (value == summary.maximum) {",
      "            ++summary.maximizing_strings;",
      "        }",
      "        if (primitive(word) && value > summary.primitive_maximum) {",
      "            summary.primitive_maximum = value;",
      "            summary.primitive_first = word;",
      "        }",
      "        if (!primitive(word) && value > summary.nonprimitive_maximum) {",
      "            summary.nonprimitive_maximum = value;",
      "            summary.nonprimitive_first = word;",
      "        }",
      "        return;",
      "    }",
      "    for (unsigned char letter = 0; letter <= largest + 1; ++letter) {",
      "        word[index] = letter;",
      "        enumerate(word, index + 1, std::max(largest, letter), summary);",
      "    }",
      "}",
      "",
      "static std::string text(const std::vector<unsigned char>& word) {",
      "    std::ostringstream out;",
      "    for (unsigned char letter : word) out << static_cast<int>(letter);",
      "    return out.str();",
      "}",
      "",
      "int main(int argc, char** argv) {",
      "    if (argc != 2) return 2;",
      "    const int maximum_length = std::stoi(argv[1]);",
      "    for (int n = 1; n <= maximum_length; ++n) {",
      "        Summary summary;",
      "        std::vector<unsigned char> word(n, 0);",
      "        enumerate(word, 1, 0, summary);",
      "        std::cout << \"length=\" << n",
      "                  << \" rgs=\" << summary.restricted_growth_strings",
      "                  << \" maximum=\" << summary.maximum",
      "                  << \" maximizing_rgs=\" << summary.maximizing_strings",
      "                  << \" first=\" << text(summary.first)",
      "                  << \" primitive_maximum=\" << summary.primitive_maximum",
      "                  << \" primitive_first=\" << text(summary.primitive_first)",
      "                  << \" nonprimitive_maximum=\" << summary.nonprimitive_maximum",
      "                  << \" nonprimitive_first=\" << text(summary.nonprimitive_first)",
      "                  << \"\\n\";",
      "    }",
      "}"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": null,
    "locator": "Independent self-contained C++17 source executed on macOS arm64 on 2026-07-28"
  },
  "models": [],
  "continuation": null,
  "relations": [
    {
      "slug": "R133",
      "title": "Exact maxima for every alphabet through length fourteen",
      "object_type": "claim",
      "relation": "evidences",
      "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: Independent self-contained C++17 source executed on macOS arm64 on 2026-07-28
License: CC0-1.0
Public record: R126
Stable alias: cds-artifact-rgs-direct-replay
Projection: Reproduction fields are derived from the immutable record.

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