Comment by Gehinnn | Hacker News Reader

Comment by Gehinnn | Hacker News Reader

This reminds me of primitive words [1]: A primitive word is a word that is not the (2+ times) repetition of any other word. This is slightly different than a non-pattern word from the article, which is a word that is not a 3+ times repetition of any other word.

The anti-pattern game is about extending words such that they do not contain a pattern word.

I wonder how the situation changes if 2 times repetitions would count as pattern (i.e. non-primitive words).

For primitive words, it is an open problem if the language of primitive words (over any non-trivial finite alphabet) is context free.

I wonder if the language of words that don't contain patterns (or non-primitive words) is context free.

[1] https://arxiv.org/abs/1104.4427

> I wonder how the situation changes if 2 times repetitions would count as pattern

I might be misunderstanding, but do you mean that you cannot even have two of the same colour in a row? This is a very simple win for first player:

W B W ?

Yes, seems like there are only finitely many words over a binary alphabet that do not contain a non-primitive word (0, 01, 010 and 1, 10, 101). How would it change if the alphabet has three symbols?

It certainly seems like you can get much longer words. I just had a quick go and came up with

  0 1 0 2 0 1 2 0 1 0 2 0 2 1

but I stopped there because it gets tedious to check manually for repetition. Might be worth writing a little script to produce the word where each letter is the smallest possible number that doesn't create repetition.

Just checked with AI: Thue showed 1906 that there are infinitely many square free words (:= a word that doesn't contain a non-primitive word) over an alphabet with at least 3 symbols.

Cool! This paper is also quite readable: https://arxiv.org/pdf/2104.04841

On p.2 they follow my idea of adding the lowest possible letter at the end, although they generalise it to adding the letter as close to the end as possible. They conjecture that this process does not stop. I'm always amazed with combinatorics how quickly you arrive at questions that no one knows the answer to.

Reply on news.ycombinator.com