A317167 Number of distinct critical exponents possible, over all binary strings of length n.

1, 2, 3, 3, 5, 6, 9, 11, 14, 16, 20, 21, 27, 30, 33, 36, 44, 47, 55, 58, 63, 67, 76, 80, 89, 94

Offset

1,2

Comments

A string x has period p if x[i]=x[i+p] for all i that make sense. The shortest period is called "the" period. The exponent exp(x) of a string x of length n is defined to be n/p, where p is the period. The critical exponent of a string x is the maximum, over all nonempty contiguous subwords w of x, of exp(w).

Links

Table of n, a(n) for n=1..26.

Example

For n = 6, there are 5 possible critical exponents:  6 (for 000000), 5 (for 000001), 4 (for 000011), 3 (for 000111), 2 (for 001001), and 5/2 (for 001010).

Prog

(Python)
from itertools import product
from fractions import Fraction
from functools import lru_cache
def period(x):
    for p in range(1, len(x)):
        if all(x[i] == x[i+p] for i in range(len(x)-p)):
            return p
    return len(x)
def exp(x):
    return Fraction(len(x), period(x))
@lru_cache(maxsize=None)
def critexp(x):
    if len(x) == 1: return 1
    return max(exp(x), critexp(x[:-1]), critexp(x[1:]))
def a(n):
    return len(set(critexp("0"+"".join(x)) for x in product("01", repeat=n-1)))
print([a(n) for n in range(1, 19)]) # Michael S. Branicky, Dec 24 2022

Crossrefs

Sequence in context: A300446 A039876 A239312 * A070830 A039862 A018051

Adjacent sequences: A317164 A317165 A317166 * A317168 A317169 A317170

Keyword

nonn,more

Author

Jeffrey Shallit, Jul 23 2018

Extensions

a(21)-a(26) from Michael S. Branicky, Dec 24 2022

Status

approved