A096365 Maximum number of iterations of the RUNS transform needed to reduce any binary sequence of length n to a sequence of length 1.

0, 2, 3, 4, 5, 5, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12

Offset: 1

Author

John W. Layman, Jul 01 2004

Keywords

• nonn

Comments

The RUNS transform maps a finite word (or sequence) x to the (finite) sequence y whose i-th term is the length of the i-th subsequence of consecutive identical terms of x. (Example: RUNS{1,2,2,2,1,1,3,3,1}={1,3,2,2,1})

Examples

			The following example shows that a(21)>=9:
  x={100110100100110110100}
  RUNS(x)={12211212212112}
  RUNS^2(x)={1221121121}
  RUNS^3(x)={1221211}
  RUNS^4(x)={12112}
  RUNS^5(x)={1121}
  RUNS^6(x)={211}
  RUNS^7(x)={12}
  RUNS^8(x)={11}
  RUNS^9(x)={2}
Since calculation shows that no other binary sequence of length 21 requires more than 9 iterations of RUNS to reduce it to a single term, we have a(21)=9.
		

Crossrefs

Cf. A319412.

Extensions

More terms (using A319412 b-file) from Pontus von Brömssen, Mar 02 2025