A225681
Number of binary words of length n that are not rich.
Original entry on oeis.org
0, 0, 0, 0, 0, 0, 0, 0, 4, 24, 92, 292, 850, 2276, 5766, 13968, 32690, 74368, 165442, 361104, 776116, 1646566, 3456030, 7189232, 14844878, 30464914
Offset: 0
- Amy Glen, Jacques Justin, Steve Widmer and Luca Q. Zamboni, Palindromic richness, arXiv:0801.1656 [math.CO]
A348664
Numbers whose binary expansion is not rich.
Original entry on oeis.org
203, 211, 300, 308, 333, 357, 395, 406, 407, 419, 422, 423, 459, 467, 556, 564, 600, 601, 604, 616, 617, 628, 653, 666, 667, 669, 690, 709, 714, 715, 723, 741, 779, 787, 790, 791, 803, 811, 812, 813, 814, 815, 820, 835, 838, 839, 844, 845, 846, 847, 851, 869
Offset: 1
For n = 203:
- the binary expansion of 203 is "11001011" and has 8 binary digits,
- we have the following 8 palindromes: "", "0", "1", "00", "11", "010", "101", "1001"
- so 203 is not rich, and belongs to this sequence.
For n = 204:
- the binary expansion of 204 is "11001100" and has 8 binary digits,
- we have the following 9 palindromes: "", "0", "1", "00", "11", "0110", "1001", "001100", "110011"
- so 204 is rich, and does not belong to this sequence.
-
Select[Range@1000,Length@Select[Union[Subsequences[s=IntegerDigits[#,2]]],PalindromeQ]<=Length@s&] (* Giorgos Kalogeropoulos, Oct 29 2021 *)
-
is(n) = { my (b=binary(n), p=select(w->w==Vecrev(w), setbinop((i,j)->b[i..j],[1..#b]))); #b!=#p }
-
def ispal(s): return s == s[::-1]
def ok(n):
s = bin(n)[2:]
return len(s) >= 1 + len(set(s[i:j] for i in range(len(s)) for j in range(i+1, len(s)+1) if ispal(s[i:j])))
print([k for k in range(870) if ok(k)]) # Michael S. Branicky, Oct 29 2021
A306314
Number of length-n binary words w such that ww is rich.
Original entry on oeis.org
2, 4, 8, 16, 32, 52, 100, 160, 260, 424, 684, 988, 1588, 2342, 3458, 5072, 7516, 10546, 15506, 21496, 30682, 42508, 60170, 81316, 114182, 153768, 212966, 283502, 390168, 513652
Offset: 1
- A. Glen, J. Justin, S. Widmer, and L. Q. Zamboni, Palindromic richness, European J. Combinatorics 30 (2009), 510-531. See Theorem 3.1, p. 515.
-
from itertools import product
def pal(w): return w == w[::-1]
def rich(w):
subs = (w[i:j] for i in range(len(w)) for j in range(i+1, len(w)+1))
return len(w) == sum(pal(s) for s in set(subs))
def a(n):
binn = ("0"+"".join(b) for b in product("01", repeat=n-1))
return sum(2 for w in binn if rich(w+w))
print([a(n) for n in range(1, 16)]) # Michael S. Branicky, Jul 07 2022
A306316
Number of length-n binary words such that every conjugate (cyclic shift) is rich.
Original entry on oeis.org
2, 4, 8, 16, 32, 64, 128, 224, 404, 684, 1124, 1732, 2680, 4078, 6338, 9072, 13160, 18502, 26830, 36936, 51850, 70228, 97246, 129940, 178782, 235980, 320858, 419190, 563936, 732472, 979602, 1262128
Offset: 1
A384371
Number of rich ternary words of length n.
Original entry on oeis.org
1, 3, 9, 27, 75, 201, 513, 1269, 3033, 7047, 15903, 35031, 75291, 158487, 326889, 662259, 1318803, 2585931, 4996251, 9524343, 17925495, 33341619, 61324821, 111624927, 201179643, 359232897, 635814867, 1116019719, 1943414733, 3358893675, 5763797829
Offset: 0
- A. Glen, J. Justin, S. Widmer and L. Q. Zamboni, Palindromic richness, European Journal of Combinatorics, 30 (2009), 510-531.
- M. Rubinchik and A. M. Shur, EERTREE: An efficient data structure for processing palindromes in strings, European Journal of Combinatorics, 68 (2018), 249-265.
- J. Rukavicka, On the number of rich words. In: É. Charlier, J. Leroy, and M. Rigo (eds) Developments in Language Theory, DLT 2017, Lecture Notes in Computer Science, vol. 10396, pp. 345-352, Springer, 2017.
-
from itertools import product
def rich(w):
subs = (w[i:j] for i in range(len(w)) for j in range(i+1, len(w)+1))
return len(w) == sum(1 for s in set(subs) if s == s[::-1])
def a(n):
if n == 0: return 1
return sum(3 for b in product("012", repeat=n-1) if rich("0"+"".join(b)))
print([a(n) for n in range(13)]) # Michael S. Branicky, May 27 2025
Showing 1-5 of 5 results.
Comments