A079101 A repetition-resistant sequence.

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

Offset: 1

Author

Clark Kimberling, Jan 03 2003

Keywords

• nonn

Comments

a(n) = 0 or 1, chosen so as to maximize the number of different subsequences that are formed.

a(n+1)=1 if and only if (a(1),a(2),...,a(n),0), but not (a(1),a(2),...,a(n),1), has greater length of longest repeated segment than (a(1),a(2),...,a(n)) has.

In Feb, 2003, Alejandro Dau solved Problem 3 on the Unsolved Problems and Rewards website, thus establishing that every binary word occurs infinitely many times in this sequence.

Klaus Sutmer remarks (Jun 26 2006) that this sequence is very similar to the Ehrenfeucht-Mycielski sequence A007061. Both sequences have every finite binary word as a factor; in fact, essentially the same proof works for both sequences.

Differs from A334941 for the first time at n = 70. - Jeffrey Shallit, Dec 14 2022

Examples

			a(7)=1 because (0,1,0,0,0,1,0) has repeated segment (0,1,0) of length 3, whereas (0,1,0,0,0,1,1) has no repeated segment of length 3.
		

Links

• Peter J. C. Moses, Table of n, a(n) for n = 1..10000
• A. Dau, Secuencia Maximizadora de Subcadenas (Interactive Java generator of repetition-resistant sequences). [Broken link]
• Clark Kimberling, Unsolved Problems and Rewards.
• Clark Kimberling, Problem 2289, Crux Mathematicorum 23 (1997) 501.

Crossrefs

Cf. A079136, A079335, A079336, A079337, A079338, A007061, A334941.