# What is longest string with no equidistant pairs of equal characters for a given alphabet?

Given a finite alphabet $A$ with $|A|=n$, what is the largest $l$ so that a string $s=a_1...a_l$ of length $l$ exists with $a_i\in A$ so that there is no $i,j,d$ with $i\neq j, d > 0$ so that $a_i = a_{i+d}$ and $a_j = a_{j+d}$?

Thanks to @greybeard I now know that such strings are called 2-surprising strings. More information can be found here: http://oeis.org/A008062

This problem has been described by Dennis E. Shasha on page 122 of the December 2003 issue of Scientific American.

Furthermore there exists a proof that $l<3n$: http://aleph0.clarku.edu/~djoyce/mpst/surprising/

These are known strings for small $n$:

n   l quantity  example

1   2   1       00
2   4   3       0010
3   7   4       0012102
4   10  2       0112032310
5   12  212     001232410431
6   15  770     001231452503410
7   18  1630    001231456264035102
8   21  1396    010234563742761154032
9   24  312     012334546785281076142053

• The question doesn't strike me as being computer science. Sounds more like math. – Yuval Filmus Jan 5 '16 at 16:36
• @yuval-filmus As long as it is a problem on strings and CNF-SAT is used to solve it, there is at least a bit of CS in it... – J.-E. Pin Jan 5 '16 at 17:25
• DId you find out anything more? Is this an open problem? If so, reposting on Theoretical Computer Science or MathOverflow may be appropriate. – Raphael May 24 '16 at 9:52