|
%I M0555 #66 Jan 31 2024 16:09:08
%S 1,2,3,4,6,8,10,13,17,21,27,30,37,47,57,62,75,87,102,116,135,155,180,
%T 194,220,254,289,312,359,392,438,479,538,595,664,701,772,863,956,1005,
%U 1115,1205,1317,1414,1552,1677,1836,1920,2074,2249,2444
%N Number of distinct autocorrelations of binary words of length n.
%C Conjecture: a(n + 1) - a(n) < a(n + 13) - a(n + 12) for all n >= 1. - _Eric Rowland_, Nov 24 2021
%C From _Eric Rivals_, Jul 11 2023: (Start)
%C 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.
%C An autocorrelation is a binary encoding of the period set.
%C 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)
%D R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley Publ., 2nd Ed., 1994. Section 8.4: Flipping Coins
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H E-Hern Lee, <a href="/A005434/b005434.txt">Table of n, a(n) for n = 1..654</a>
%H L. J. Guibas, <a href="http://dx.doi.org/10.1007/978-3-642-82456-2_17">Periodicities in Strings</a>, Combinatorial Algorithms on Words 1985, NATO ASI Vol. F12, 257-269
%H L. J. Guibas and A. M. Odlyzko, <a href="http://dx.doi.org/10.1016/0097-3165(81)90038-8">Periods in Strings</a>, Journal of Combinatorial Theory A 30:1 (1981) 19-42.
%H Leo J. Guibas and Andrew M. Odlyzko, <a href="http://dx.doi.org/10.1016/0097-3165(81)90005-4">String overlaps, pattern matching and nontransitive games</a>, Journal of Combinatorial Theory Series A, 30 (March 1981), 183-208.
%H H. Harborth, <a href="http://gdz.sub.uni-goettingen.de/dms/resolveppn/?PPN=GDZPPN002189852">Endliche 0-1-Folgen mit gleichen Teilblöcken</a>, Journal für Mathematik, 271 (1974) 139-154.
%H A. Kaseorg, <a href="https://codegolf.stackexchange.com/a/127038/39244">Rust program used to compute values for n up to 500</a>
%H E. Rivals, and S. Rahmann (2001). <a href="https://doi.org/10.1007/3-540-48224-5_51">Combinatorics of Periods in Strings</a>. In: Orejas, F., Spirakis, P.G., van Leeuwen, J.(eds) Automata, Languages and Programming. ICALP 2001. Lecture Notes in Computer Science, vol 2076. Springer, Berlin, Heidelberg. doi:10.1007/3-540-48224-5_51.
%H E. H. Rivals and S. Rahmann, <a href="http://dx.doi.org/10.1016/S0097-3165(03)00123-7">Combinatorics of Periods in Strings</a>, Journal of Combinatorial Theory - Series A, Vol. 104(1) (2003), pp. 95-113.
%H E. H. Rivals, <a href="http://www.lirmm.fr/~rivals/RESEARCH/PERIOD/">Autocorrelation of Strings</a>.
%H E. H. Rivals and S. Rahmann <a href="http://www.lirmm.fr/~rivals/PUBLI/FILES/RivalsRahmannJCTA03.pdf">Combinatorics of Periods in Strings</a>
%H E. Rivals, M. Sweering, and P. Wang, <a href="https://doi.org/10.4230/LIPIcs.ICALP.2023.100">Convergence of the Number of Period Sets in Strings</a>. 50th International Colloquium on Automata, Languages, and Programming, {ICALP} 2023, Leibniz International Proceedings in Informatics (LIPIcs), ICALP 2023: 100:1-100:14. doi:<a href="https://doi.org/10.4230/LIPIcs.ICALP.2023.100">10.4230/LIPIcs.ICALP.2023.100</a>
%H T. Sillke, <a href="http://www.mathematik.uni-bielefeld.de/~sillke/SEQUENCES/autocorrelation-range.c">Autocorrelation Range</a>
%H T. Sillke, <a href="http://www.mathematik.uni-bielefeld.de/~sillke/SEQUENCES/kappa">kappa sequence for words of length n</a>
%H T. Sillke, <a href="http://www.mathematik.uni-bielefeld.de/~sillke/SEQUENCES/series018">The autocorrelation function</a>
%e From _Eric Rowland_, Nov 22 2021: (Start)
%e For n = 5 there are a(5) = 6 distinct autocorrelations of length-5 binary words:
%e 00000 can overlap itself in 1, 2, 3, 4, or 5 letters. Its autocorrelation is 11111.
%e 00100 can overlap itself in 1, 2, or 5 letters. Its autocorrelation is 10011.
%e 01010 can overlap itself in 1, 3, or 5 letters. Its autocorrelation is 10101.
%e 00010 can overlap itself in 1 or 5 letters. Its autocorrelation is 10001.
%e 01001 can overlap itself in 2 or 5 letters. Its autocorrelation is 10010.
%e 00001 can only overlap itself in 5 letters. Its autocorrelation is 10000.
%e (End)
%p A005434 := proc( n :: posint )
%p local S := table();
%p for local c in Iterator:-BinaryGrayCode( n ) do
%p c := convert( c, 'list' );
%p S[ [seq]( evalb( c[ 1 .. i + 1 ] = c[ n - i .. n ] ), i = 0 .. n - 1 ) ] := 0
%p end do;
%p numelems( S )
%p end proc: # _James McCarron_, Jun 21 2017
%t 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 *)
%Y Cf. A018819 (related to a lower bound for autocorrelations), A045690 (the number of binary strings sharing the same autocorrelation).
%K nonn,nice
%O 1,2
%A _Simon Plouffe_, _N. J. A. Sloane_
%E More terms and additional references from torsten.sillke(at)lhsystems.com
%E Definition clarified by _Eric Rowland_, Nov 22 2021
|
