|
| |
|
|
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
|
|
|
|
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
|
|
|
|
KEYWORD
|
nonn,base,hard
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
