login
Lengths of successive runs of equal terms in A373811.
4

%I #32 Aug 19 2024 12:12:59

%S 1,2,3,3,5,4,6,5,7,6,7,8,8,7,8,9,9,8,9,11,9,10,10,9,12,11,10,11,12,12,

%T 12,12,11,12,13,13,12,13,13,14,13,14,14,16,13,13,14,15

%N Lengths of successive runs of equal terms in A373811.

%C Equivalently, a(n) is the number of occurrences of the term n-1 in A373811. - _Max Alekseyev_, Aug 15 2024

%C Comment from _Dominic McCarty_, Aug 15 2024 (Start)

%C Theorem: a(n) <= n.

%C Proof. Let S(n) denote a smallest set of lines that intersects all points (m, A373811(m)) for m < n.

%C Let k and j be integers such that {(k, A373811(k)), (k+1, A373811(k+1)), ... (k+j, A373811(k+j))} form a run of equal terms at height h.

%C We know that S(k+j) has h lines in it by definition.

%C I show below that S(k+j) contains no horizontal line of the form y = h, so each line in S(k+j) intersects the line y = h exactly once.

%C So S(k+j) intersects the line y = h at most h times. This means that once h + 1 points appear along the line y = h, we must introduce a new line to intersect all those points. So run lengths of A373811 at height h can be at most h+1.

%C It appears that equality only happens at heights 0, 1, 2, and 4 (corresponding to a(1), a(2), a(3) and a(5) here.

%C Proof that S(k+j) contains no horizontal line of the form y = h: Assume the contrary. By definition, S(k+j) must intersect all points left of x = k+j, so it must also intersect all points left of x = k. But y = h intersects no points left of x = k. So S(k+j) \ {y = h} intersects all points left of x = k. This means that |S(k)| is at most |S(k+j) \ {y = h}| = h - 1. However, A373811(k) = h and A373811(k) = |S(k)|. Contradiction! (End)

%Y Cf. A373811.

%K nonn,more

%O 1,2

%A _N. J. A. Sloane_, Aug 14 2024

%E a(9)-a(10) corrected, a(18)-a(48) added by _Max Alekseyev_, Aug 18 2024