OFFSET
0
COMMENTS
a(n) is conjectured to be normal by virtue of its construction.
The C code below takes O(n^2) time and O(n) space to generate the first n terms.
LINKS
Aresh Pourkavoos, Table of n, a(n) for n = 0..8191
EXAMPLE
The empty sequence has no tails followed by 0 or 1, so a(0)=0 by default.
The sequence (0) contains (the empty sequence plus) 0 once and 1 zero times, so a(1)=1.
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.
In (0, 1, 0), 0 is followed by 0 zero times and by 1 once, so a(3)=0.
PROG
(C)
#include <stdio.h>
#define N_TERMS 8192
// Stores generated terms
int a[N_TERMS];
// b[j-1] is the number of bits before (not including) a[n-j]
// which match the tail of the first n entries
int b[N_TERMS];
// c induces a linked list structure on b
// with an extra node to make it cyclic
// Indices are offset by 1 since the extra node is in front
int c[N_TERMS];
int cEnd = 0;
int main() {
FILE *bfile = fopen("b330731.txt", "w+");
for (int n = 0; n < N_TERMS; n++) {
// Append new digit to list from previous loop
// or (n = 0) initialize c
c[n] = 0;
c[cEnd] = n;
cEnd = n;
// Find new digit by iterating over b
// using the indices given in c
int newD = 0;
int freq0 = 0;
int freq1 = 0;
int prevTail = -1;
int j = c[0];
while (j != 0) {
int currTail = b[j-1];
if (currTail != prevTail) {
// All tails of a given length have been accumulated in freqs,
// so they need to be compared to decide whether to continue
if (freq1 != freq0) {
break;
}
freq0 = 0;
freq1 = 0;
}
// Use digit that comes after current tail to adjust freqs
if (a[n-j] == 0) {
freq0++;
} else {
freq1++;
}
prevTail = currTail;
j = c[j];
}
// 0 is chosen by default (if freq1 == freq0)
if (freq1 < freq0) {
newD = 1;
}
// Update matching tail lengths
j = 0;
for (int numVisited = 0; numVisited < n; numVisited++) {
int k = c[j];
if (a[n-k] == newD) {
// Matching tail grows by 1, position in list is unaffected
b[k-1]++;
j = k;
} else {
// Matching tail resets to 0, moved to back of list
b[k-1] = 0;
c[j] = c[k];
if (cEnd == k) {
cEnd = j;
}
c[k] = 0;
c[cEnd] = k;
cEnd = k;
}
}
a[n] = newD;
b[n] = 0;
printf("%d", newD);
fprintf(bfile, "%d %d\n", n, newD);
}
printf("\n");
fclose(bfile);
return 0;
} // rewritten by Aresh Pourkavoos, Dec 21 2021
CROSSREFS
KEYWORD
nonn
AUTHOR
Aresh Pourkavoos, Dec 28 2019
STATUS
approved