A330731 - OEIS

%I #28 Jan 18 2022 21:52:25

%S 0,1,0,0,1,1,0,1,1,1,0,0,0,1,0,1,0,0,0,0,1,1,1,1,0,1,0,1,1,0,0,1,0,0,

%T 0,1,1,0,0,0,0,0,1,0,0,1,0,1,1,1,1,1,0,0,1,1,1,0,1,1,0,1,0,0,1,1,1,1,

%U 1,1,0,1,1,1,1,0,0,0,0,1,0,1,1,0

%N Binary sequence created by greedily remaining as normal as possible: starting with the empty sequence, repeatedly find the longest tail (or suffix) which is followed by one digit more frequently than the other, and append the digit which follows said tail less often. 0 is appended if no such inequality is found.

%C a(n) is conjectured to be normal by virtue of its construction.

%C The C code below takes O(n^2) time and O(n) space to generate the first n terms.

%H Aresh Pourkavoos, <a href="/A330731/b330731.txt">Table of n, a(n) for n = 0..8191</a>

%e The empty sequence has no tails followed by 0 or 1, so a(0)=0 by default.

%e The sequence (0) contains (the empty sequence plus) 0 once and 1 zero times, so a(1)=1.

%e The sequence (0, 1) does not contain 1 followed by any digit, and it contains (the empty sequence plus) 0 and 1 an equal number of times, so a(2)=0 by default.

%e In (0, 1, 0), 0 is followed by 0 zero times and by 1 once, so a(3)=0.

%o (C)

%o #include <stdio.h>

%o #define N_TERMS 8192

%o // Stores generated terms

%o int a[N_TERMS];

%o // b[j-1] is the number of bits before (not including) a[n-j]

%o // which match the tail of the first n entries

%o int b[N_TERMS];

%o // c induces a linked list structure on b

%o // with an extra node to make it cyclic

%o // Indices are offset by 1 since the extra node is in front

%o int c[N_TERMS];

%o int cEnd = 0;

%o int main() {

%o   FILE *bfile = fopen("b330731.txt", "w+");

%o   for (int n = 0; n < N_TERMS; n++) {

%o     // Append new digit to list from previous loop

%o     // or (n = 0) initialize c

%o     c[n] = 0;

%o     c[cEnd] = n;

%o     cEnd = n;

%o     // Find new digit by iterating over b

%o     // using the indices given in c

%o     int newD = 0;

%o     int freq0 = 0;

%o     int freq1 = 0;

%o     int prevTail = -1;

%o     int j = c[0];

%o     while (j != 0) {

%o       int currTail = b[j-1];

%o       if (currTail != prevTail) {

%o         // All tails of a given length have been accumulated in freqs,

%o         // so they need to be compared to decide whether to continue

%o         if (freq1 != freq0) {

%o           break;

%o         }

%o         freq0 = 0;

%o         freq1 = 0;

%o       }

%o       // Use digit that comes after current tail to adjust freqs

%o       if (a[n-j] == 0) {

%o         freq0++;

%o       } else {

%o         freq1++;

%o       }

%o       prevTail = currTail;

%o       j = c[j];

%o     }

%o     // 0 is chosen by default (if freq1 == freq0)

%o     if (freq1 < freq0) {

%o       newD = 1;

%o     }

%o     // Update matching tail lengths

%o     j = 0;

%o     for (int numVisited = 0; numVisited < n; numVisited++) {

%o       int k = c[j];

%o       if (a[n-k] == newD) {

%o         // Matching tail grows by 1, position in list is unaffected

%o         b[k-1]++;

%o         j = k;

%o       } else {

%o         // Matching tail resets to 0, moved to back of list

%o         b[k-1] = 0;

%o         c[j] = c[k];

%o         if (cEnd == k) {

%o           cEnd = j;

%o         }

%o         c[k] = 0;

%o         c[cEnd] = k;

%o         cEnd = k;

%o       }

%o     }

%o     a[n] = newD;

%o     b[n] = 0;

%o     printf("%d", newD);

%o     fprintf(bfile, "%d %d\n", n, newD);

%o   }

%o   printf("\n");

%o   fclose(bfile);

%o   return 0;

%o } // rewritten by _Aresh Pourkavoos_, Dec 21 2021

%Y Could have similar applications to A099601, A166316: testing many different binary sequences efficiently, except the sequence length is unknown.

%K nonn

%O 0

%A _Aresh Pourkavoos_, Dec 28 2019