OFFSET
1,2
COMMENTS
"A word w is privileged if (a) it has length <= 1, or (b) it has a privileged border that appears exactly twice in w." - from the Forsyth et al. paper.
The first terms which differ from "palindromes over the alphabet {1,2}" (not in the OEIS) are the four 8 digit terms a({48, 49, 60, 61}) = {11212211, 11221211, 22112122, 22121122}, then come 9 digit terms a(71) = 112122211, etc. The first palindromes not in the sequence are the 14-digit terms {11212211221211, 11221211212211, 22112122121122, 22121122112122}. - M. F. Hasler, Nov 02 2020
LINKS
Michael S. Branicky, Table of n, a(n) for n = 1..13752 (terms with <= 18 digits; terms 1..4232 from Lars Blomberg)
M. Forsyth, A. Jayakumar, and J. Shallit, Remarks on Privileged Words, arXiv preprint arXiv:1311.7403 [cs.FL], 2013.
J. Peltomäki, Introducing privileged words: privileged complexity of Sturmian words, Theoret. Comput. Sci. 500 (2013), 57-67.
PROG
(PARI) is_A235609(w, n, p)={n || if(#setminus(Set(p=digits(w)), [1, 2]), return, w=fromdigits([d-1|d<-p], 2); n=#p; p[1]>1 && w=2^n-1-w); !w|| setsearch([2^(n-1)-2, 2^(n-1)+1, 2^n-1], w)|| for(i=1, n-2, (w-p=w>>i)%2^(n-i)&&next; for(j=1, i-1, (w>>j-p)%2^(n-i)||next(2)); is_A235609(p, n-i)&&return(1))} \\ M. F. Hasler, Nov 02 2020
(Python)
from itertools import count, islice, product
def comp(w): return "".join("2" if c == "1" else "1" for c in w)
def agen():
priv = set("1"); yield from [1, 2]
for d in count(2):
found = []
for p in product("12", repeat=d-1):
w, passes = "1" + "".join(p), False
if len(set(w)) == 1: passes = True
elif len(w.lstrip(w[0])) != len(w.rstrip(w[0])): passes = False
else:
for i in range(1, len(w)):
p, s = w[:i], w[-i:]
if p == s and p not in w[1:-1] and p in priv:
passes = True; break
if passes: found.append(w); priv.add(w)
yield from (int(w) for w in found)
yield from sorted(int(comp(w)) for w in found)
print(list(islice(agen(), 37))) # Michael S. Branicky, Jul 01 2022
CROSSREFS
KEYWORD
nonn
AUTHOR
N. J. A. Sloane, Jan 23 2014
EXTENSIONS
a(29)-a(37) from Lars Blomberg, Jun 16 2017
STATUS
approved