cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

A316936 a(n) is the maximum state complexity of the language C(w) of conjugates of w, over all length-n binary strings w.

This page as a plain text file.
%I A316936 #38 May 25 2023 01:27:15
%S A316936 3,5,7,11,15,21,29,39,49,61,75,91,109,129,151,175,199,225,253,283,315,
%T A316936 349,385,423,463,505,549,595,643,693,745,799,853,909,967,1027,1089,
%U A316936 1153,1219,1287,1357,1429,1503,1579,1657,1737,1819,1903,1989,2077,2167,2259
%N A316936 a(n) is the maximum state complexity of the language C(w) of conjugates of w, over all length-n binary strings w.
%C A316936 Two strings are conjugate if one is a cyclic shift of the other, such as "listen" and "enlist".
%C A316936 If w is a string, then C(w) is the set of all conjugates of w. Thus C(001) = {001, 100, 010}.
%C A316936 The state complexity of a finite set of strings S is the size (i.e., the number of states) of the smallest (complete) deterministic finite automaton (DFA) recognizing S.
%H A316936 D. Gabric, S. Holub, and J. Shallit, <a href="https://arxiv.org/abs/1903.05442">Generalized de Bruijn words and the state complexity of conjugate sets</a>, arXiv:1903.05442 [cs.FL], March 13 2019.
%F A316936 a(n) = n^2 - (2i-3)2^i - j(2i+1) - 1 = 2^{2i} + (2j-2i+3)2^i + j^2 - (2i+1)j - 1, if n = 2^i + j with 0 <= j < 2^i.
%Y A316936 Cf. A317586.
%K A316936 nonn
%O A316936 1,1
%A A316936 _Jeffrey Shallit_, Jul 21 2018