login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 59th year, we have over 358,000 sequences, and we’ve crossed 10,300 citations (which often say “discovered thanks to the OEIS”).

Other ways to Give
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005434 Number of distinct autocorrelations of binary words of length n.
(Formerly M0555)
8
1, 2, 3, 4, 6, 8, 10, 13, 17, 21, 27, 30, 37, 47, 57, 62, 75, 87, 102, 116, 135, 155, 180, 194, 220, 254, 289, 312, 359, 392, 438, 479, 538, 595, 664, 701, 772, 863, 956, 1005, 1115, 1205, 1317, 1414, 1552, 1677, 1836, 1920, 2074, 2249, 2444 (list; graph; refs; listen; history; text; internal format)
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

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

L. J. Guibas, Periodicities in Strings, Combinatorial Algorithms on Words 1985, NATO ASI Vol. F12, 257-269

L. J. Guibas and A. M. Odlyzko, Periods in Strings, Journal of Combinatorial Theory A 30:1 (1981) 19-42.

Leo J. Guibas and Andrew M. Odlyzko, String overlaps, pattern matching and nontransitive games, Journal of Combinatorial Theory Series A, 30 (March 1981), 183-208.

H. Harborth, Endliche 0-1-Folgen mit gleichen Teilblöcken, Journal für Mathematik, 271 (1974) 139-154.

A. Kaseorg, Rust program used to compute values for n up to 500

E. H. Rivals and S. Rahmann, Combinatorics of Periods in Strings, Journal of Combinatorial Theory - Series A, Vol. 104(1) (2003), pp. 95-113.

E. H. Rivals, Autocorrelation of Strings.

E. H. Rivals and S. Rahmann Combinatorics of Periods in Strings

T. Sillke, Autocorrelation Range

T. Sillke, kappa sequence for words of length n

T. 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

Cf. A018819 (related to a lower bound for autocorrelations), A045690 (the number of binary strings sharing the same autocorrelation).

Sequence in context: A325350 A027585 A123015 * A027589 A039851 A239100

Adjacent sequences: A005431 A005432 A005433 * A005435 A005436 A005437

KEYWORD

nonn,nice

AUTHOR

Simon Plouffe, N. J. A. Sloane

EXTENSIONS

More terms and additional references from torsten.sillke(at)lhsystems.com

Definition clarified by Eric Rowland, Nov 22 2021

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 7 10:26 EST 2022. Contains 358656 sequences. (Running on oeis4.)