OFFSET
1,2
COMMENTS
Equivalently, a(n) is the number of occurrences of the term n-1 in A373811. - Max Alekseyev, Aug 15 2024
Comment from Dominic McCarty, Aug 15 2024 (Start)
Theorem: a(n) <= n.
Proof. Let S(n) denote a smallest set of lines that intersects all points (m, A373811(m)) for m < n.
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.
We know that S(k+j) has h lines in it by definition.
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.
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.
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.
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)
CROSSREFS
KEYWORD
nonn,more
AUTHOR
N. J. A. Sloane, Aug 14 2024
EXTENSIONS
a(9)-a(10) corrected, a(18)-a(48) added by Max Alekseyev, Aug 18 2024
STATUS
approved