OFFSET
1,1
COMMENTS
A Dean word is a reduced word that does not contain occurrences of ww for any nonempty w.
a(n) is a multiple of 4 by symmetry. - Michael S. Branicky, Jun 20 2022
LINKS
Martin Ehrenstein, Table of n, a(n) for n = 1..64
Richard A. Dean, A sequence without repeats on x, x^{-1}, y, y^{-1}, Amer. Math. Monthly 72, 1965. pp. 383-385. MR 31 #350.
Tero Harju, Avoiding Square-Free Words on Free Groups, arXiv:2104.06837 [math.CO], 2021.
PROG
(C++)
#include <iostream>
#include <vector>
bool good (const std::string& s) {
long n = s.size();
for (long i = 1; i <= n/2; i++) {
bool match = true;
for (long j = 0; j < i; j++) {
if (s[n-i+j] != s[n-2*i+j]) {
match = false; break; } }
if (match) return false; }
return true; }
std::vector<std::string> s = {"01"}, t, d = {"02", "13"};
int main () {
std::cout << "1 4\n";
for (long i = 2; i < 40; i++) {
std::cout << i << " " << 8*s.size() << "\n";
for (char c : d[i%2]) {
for (const std::string& x : s) {
if (good(x+c)) t.push_back(x+c); } }
s.swap(t); t = std::vector<std::string>(); } } // James Rayman, Apr 15 2021
(Python)
def isf(s): # incrementally squarefree (check factors ending in last letter)
for l in range(1, len(s)//2 + 1):
if s[-2*l:-l] == s[-l:]: return False
return True
def aupton(nn, verbose=False):
alst, sfs = [], set("0")
for n in range(1, nn+1):
an, eo = 4*len(sfs), ["02", "13"]
sfsnew = set(s+i for s in sfs for i in eo[n%2] if isf(s+i))
alst, sfs = alst+[an], sfsnew
if verbose: print(n, an)
return alst
print(aupton(30)) # Michael S. Branicky, Jun 20 2022
CROSSREFS
KEYWORD
nonn
AUTHOR
Michel Marcus, Apr 15 2021
EXTENSIONS
More terms from James Rayman, Apr 15 2021
STATUS
approved