OFFSET
1,2
COMMENTS
Conjecture: a(n + 1) - a(n) < a(n + 13) - a(n + 12) for all n >= 1. - Eric Rowland, Nov 24 2021
From Eric Rivals, Jul 11 2023: (Start)
log(a(n))/log^2(n) converges when n tends to infinity. This conjecture was first stated in (Guibas and Odlyzko, JCTA, 1981a). (Rivals et al. ICALP 2023) proves this conjecture and provides an improved upper bound for this ratio.
An autocorrelation is a binary encoding of the period set.
This sequence is also the number of autocorrelation for words over any finite alphabet whose cardinality is at least two. The autocorrelation is independent of the alphabet cardinality, provided the cardinality is at least two; see proofs in (Guibas and Odlyzko, JCTA, 1981a). (End)
REFERENCES
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley Publ., 2nd Ed., 1994. Section 8.4: Flipping Coins
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
E-Hern Lee, Table of n, a(n) for n = 1..654
Leo J. Guibas, Periodicities in Strings, Comb. Algor. Words, NATO ASI F 12 (1985), 257-269.
Leo J. Guibas and Andrew M. Odlyzko, Periods in Strings, J. Comb. Theory A 30(1) (1981), 19-42.
Leo J. Guibas and Andrew M. Odlyzko, String overlaps, pattern matching and nontransitive games, J. Comb. Theory A 30 (March 1981), 183-208.
Heiko Harborth, Endliche 0-1-Folgen mit gleichen Teilblöcken, J. für Mathematik, 271 (1974) 139-154.
Anders Kaseorg, Rust program used to compute values for n up to 500.
Sergey Kirgizov, Combinatorial Contemplations, hal: tel-05570783 [math.CO] Univ. Bourgogne (France, 2026). See pp. 12-13 (Cor. 5.1).
Eric Rivals, Incremental computation of the set of period sets, arXiv:2410.12077 [cs.DM], 2024. Refers to this sequence.
Eric H. Rivals, Autocorrelation of Strings.
Eric Rivals and Sven Rahmann, Combinatorics of Periods in Strings. In: F. Orejas, P. G. Spirakis, J. van Leeuwen (eds), Automata, Lang. Prog. (ICALP 2001) Springer, Lect. Notes Comp. Sci. 2076.
Eric Rivals and Sven Rahmann, Combinatorics of periods in strings, Journal of Combinatorial Theory - Series A, Vol. 104(1) (2003), pp. 95-113. See also LIRMM link.
Eric Rivals, Michelle Sweering, and Pengfei Wang, Convergence of the Number of Period Sets in Strings. 50th Int'l Colloq. Automata Lang. Prog. (ICALP 2023), Leibniz Int'l Proc. Inform. (LIPIcs) 100:1-100:14. doi:10.4230/LIPIcs.ICALP.2023.100. See also arXiv:2209.08926 [cs.DM], 2022.
Torsten Sillke, Autocorrelation Range (with C program).
Torsten Sillke, kappa sequence for words of length n, table of n, a(n) for n = 1..1025.
Torsten Sillke, The autocorrelation function.
EXAMPLE
From Eric Rowland, Nov 22 2021: (Start)
For n = 5 there are a(5) = 6 distinct autocorrelations of length-5 binary words:
00000 can overlap itself in 1, 2, 3, 4, or 5 letters. Its autocorrelation is 11111.
00100 can overlap itself in 1, 2, or 5 letters. Its autocorrelation is 10011.
01010 can overlap itself in 1, 3, or 5 letters. Its autocorrelation is 10101.
00010 can overlap itself in 1 or 5 letters. Its autocorrelation is 10001.
01001 can overlap itself in 2 or 5 letters. Its autocorrelation is 10010.
00001 can only overlap itself in 5 letters. Its autocorrelation is 10000.
(End)
MAPLE
A005434 := proc( n :: posint )
local S := table();
for local c in Iterator:-BinaryGrayCode( n ) do
c := convert( c, 'list' );
S[ [seq]( evalb( c[ 1 .. i + 1 ] = c[ n - i .. n ] ), i = 0 .. n - 1 ) ] := 0
end do;
numelems( S )
end proc: # James McCarron, Jun 21 2017
MATHEMATICA
Table[Length[Union[Map[Flatten[Position[Table[Take[#, n-i]==Drop[#, i], {i, 0, n-1}], True]-1]&, Tuples[{0, 1}, n]]]], {n, 1, 15}] (* Geoffrey Critzer, Nov 29 2013 *)
CROSSREFS
KEYWORD
nonn,nice
AUTHOR
EXTENSIONS
More terms and additional references from torsten.sillke(at)lhsystems.com
Definition clarified by Eric Rowland, Nov 22 2021
STATUS
approved
