cp's OEIS Frontend

A373812 Lengths of successive runs of equal terms in A373811.

%I A373812 #36 Mar 30 2025 04:06:20
%S A373812 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 A373812 12,12,11,12,13,13,12,13,13,14,13,14,14,16,13,13,14,15
%N A373812 Lengths of successive runs of equal terms in A373811.
%C A373812 Equivalently, a(n) is the number of occurrences of the term n-1 in A373811. - _Max Alekseyev_, Aug 15 2024
%C A373812 Comment from _Dominic McCarty_, Aug 15 2024 (Start)
%C A373812 Theorem: a(n) <= n.
%C A373812 Proof. Let S(n) denote a smallest set of lines that intersects all points (m, A373811(m)) for m < n.
%C A373812 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 A373812 We know that S(k+j) has h lines in it by definition.
%C A373812 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 A373812 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 A373812 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 A373812 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 A373812 Cf. A373811.
%K A373812 nonn,more
%O A373812 1,2
%A A373812 _N. J. A. Sloane_, Aug 14 2024
%E A373812 a(9)-a(10) corrected, a(18)-a(48) added by _Max Alekseyev_, Aug 18 2024