A280711 A pseudorandom binary sequence with minimum cyclic autocorrelation of all of its partial subsequences.

1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1

Offset

1,1

Comments

After the first term a(1) = 1, each subsequent term is chosen so as to minimize the cyclic autocorrelations of the partial sequence. If the autocorrelation doesn't change with different choices for the next term, then the complement of the previous term is used. If this sequence were to repeat the last term instead of using its complement, a similar result would be obtained, that is, a sequence with a nearly flat average Fourier spectrum, but with half the average power spectrum.

Links

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

Formula

With F(a(n)) = Sum_{i=1..n} Sum_{j=0..n-1} (2*a(i)-1)*(2*a((i+j) mod n)-1)

If argmin(F(a(n))) < argmax(F(a(n))) then

a(n) = argmin(F(a(n)))

else

a(n) = (a(n-1) + 1) mod 2

Mathematica

(* This function is the sum of all possible cyclic autocorrelations of a list x *)
AutoCorrelation[x_] :=
  Sum[Abs[x.RotateRight[x, j]], {j, 0, Length[x] - 1}];
a = {1}; (* First element *)
nmax = 120; (*number of appended elements*)
Do[If[AutoCorrelation[Append[a, 1]] < AutoCorrelation[Append[a, -1]],
   AppendTo[a, 1],
   If[AutoCorrelation[Append[a, 1]] > AutoCorrelation[Append[a, -1]],
    AppendTo[a, -1], AppendTo[a, -a[[-1]]]]], {j, nmax}];
a /. {-1 -> 0}

Crossrefs

Sequence in context: A267034 A167364 A365992 * A293164 A230298 A000480

Adjacent sequences: A280708 A280709 A280710 * A280712 A280713 A280714

Keyword

nonn,base

Author

Andres Cicuttin, Jan 07 2017

Status

approved