A373812 Lengths of successive runs of equal terms in A373811.

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, 12, 12, 11, 12, 13, 13, 12, 13, 13, 14, 13, 14, 14, 16, 13, 13, 14, 15

Offset: 1

Author

N. J. A. Sloane, Aug 14 2024

Keywords

• nonn
• more

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

Cf. A373811.

Extensions

a(9)-a(10) corrected, a(18)-a(48) added by Max Alekseyev, Aug 18 2024