login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A280816 A pseudorandom binary sequence with maximal uniformity of the distribution of all subsequences. 3
1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

after the first term a(1)=1, each subsequent term is chosen so as to minimize the variance of the histogram that accumulates the occurrences of all possible subsequences taken over the sequence considered as a circular sequence. If the variance doesn't change with different choices for the next term, then the complement of the previous term is used.

Among the first 1000 terms there are 485 1's. - Lars Blomberg, Jan 26 2017

LINKS

Lars Blomberg, Table of n, a(n) for n = 1..1000

MATHEMATICA

(* SubSeq[x, i, k] gives the Subsequence of length k starting at position i of circular sequence x *)

SubSeq[x_, i_, k_] := RotateLeft[x, i - 1][[1 ;; k]];

(* BinaryPattern[n, len] gives the n-th binary pattern of length len. *)

(* Example: The first binary pattern correspond to the digital

representation of 0 with len bits  *)

(* Note: 0 <= n <= 2^len and len >= Log[2, n] >= 1 *)

BinaryPattern[n_, len_] := IntegerDigits[n - 1, 2, len];

(* VarOfSeq[x] gives the variance of the histogram that accumulates the occurrences of all possible subsequences taken over the sequence considered as a circular sequence *)

VarOfSeq[x_] := Module[{slen, myhcomplete, myhreduced},

   slen = Length[x];

   myhcomplete =

    Table[Table[{i, j, BinaryPattern[j, i], 0}, {j, 1, 2^i  }], {i, 1,

       slen}];

   Do[Do[Do[

      If[myhcomplete[[k]][[m]][[3]] == SubSeq[x, i, k],

       myhcomplete[[k]][[m]][[4]]++]

      , {i, 1, slen}], {m, 1, 2^k  }], {k, 1, slen}];

   myhreduced =

    Table[Table[myhcomplete[[i]][[j + 1]][[4]], {j, 0, 2^i - 1 }], {i,

       1, Length[myhcomplete]}];

   (Variance@Flatten@myhreduced) // Return];

nmax=21; (* the execution time grows exponentially with the number of terms !*)

a = {1};

(* The Print function allows monitoring the progress of the algorithm's execution *)

Do[

If[VarOfSeq[Append[a, 1]] < VarOfSeq[Append[a, 0]], AppendTo[a, 1],

  If[VarOfSeq[Append[a, 1]] > VarOfSeq[Append[a, 0]], AppendTo[a, 0],

   AppendTo[a, Mod[1 + a[[-1]], 2]]]];

Print[a, " ", VarOfSeq[a] // N ], {j, 1, nmax}]

CROSSREFS

Cf. A280711.

Sequence in context: A218173 A068426 A267006 * A265246 A138709 A227998

Adjacent sequences:  A280813 A280814 A280815 * A280817 A280818 A280819

KEYWORD

nonn,base,hard

AUTHOR

Andres Cicuttin, Jan 14 2017

EXTENSIONS

More terms from Lars Blomberg, Jan 25 2017

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 15 13:37 EDT 2021. Contains 342977 sequences. (Running on oeis4.)