A373811 -id:A373811 - cp's OEIS frontend

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

N. J. A. Sloane, Aug 14 2024

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)

Cf. A373811.

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

A373813 a(n) is the smallest number of straight lines needed to intersect all points (k, prime(k)) for k = 1..n.

Original entry on oeis.org

1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 11, 11, 11, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 15

Offset: 1

Rémy Sigrist and N. J. A. Sloane, Aug 18 2024

nonn

Dan Asimov asks if the graph is trying to converge to the Cantor (or Devil's Staircase) function. - N. J. A. Sloane, Aug 25 2024

Max Alekseyev, Table of n, a(n) for n = 1..410
Max Alekseyev, Sage program for lines covering points, Github, Aug 19 2024
N. J. A. Sloane, Sketch to illustrate first 11 terms. Solutions (representing points by their X-coordinates): a(5)=2: {1,5}{2,3,4}; a(9)=3: {1,2}{3,5,7,9}{4,6,8}; a(11)=4: {1,5}{2,3,4}{6,7,10}{8,9,11}.
N. J. A. Sloane, A Nasty Surprise in a Sequence and Other OEIS Stories, Experimental Mathematics Seminar, Rutgers University, Oct 10 2024, Youtube video; Slides [Mentions this sequence]

Cf. A373814 (run lengths), A373810 (same with y(k) = phi(k)), A373811 (similar with y(k) = a(k)), A375499 (same with y(k)=sigma(k)).

See also A376187, A376188, A376190 for single lines.

Terms a(19) onward from Max Alekseyev, Aug 18 2024

A375499 a(n) is the smallest number of straight lines needed to intersect all points (k, d(k)) for k = 1..n (where d is the sum-of-divisors function A000005).

Original entry on oeis.org

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

Offset: 1

Rémy Sigrist and N. J. A. Sloane, Aug 18 2024

nonn

			The initial terms, together with an appropriate set of lines, are:
  1 1 [1]
  2 1 [x]
  3 2 [2, x]
  4 2 [2, (2/3)*x + 1/3]
  5 2 [2, (2/3)*x + 1/3]
  6 3 [2, 2*x - 8, (2/3)*x + 1/3]
  7 3 [2, 2*x - 8, (2/3)*x + 1/3]
  8 3 [2, 4, (2/3)*x + 1/3]
  9 4 [2, 3, 4, x]
  10 4 [2, 3, 4, x]
  11 4 [2, 3, 4, x]
  12 4 [2, 3, 4, (5/11)*x + 6/11]
  13 4 [2, 3, 4, (5/11)*x + 6/11]
  14 4 [2, 3, 4, (5/11)*x + 6/11]
  15 4 [2, 3, 4, (5/11)*x + 6/11]
  16 5 [2, 3, 4, 4*x - 42, (4/15)*x + 11/15]
  17 5 [2, 3, 4, 4*x - 42, (4/15)*x + 11/15]
  18 5 [2, 3, 4, 6, (4/15)*x + 11/15]

Max Alekseyev, Table of n, a(n) for n = 1..400
Max Alekseyev, Sage program for lines covering points, Github, Aug 19 2024
Rémy Sigrist, PARI program
N. J. A. Sloane, A Nasty Surprise in a Sequence and Other OEIS Stories, Experimental Mathematics Seminar, Rutgers University, Oct 10 2024, Youtube video; Slides [Mentions this sequence]

Suggested by A373811 and A375420.

Cf. A000005, A373810, A373813, A375515 (RUNS).

PARI
```
\\ See Links section.
```

Terms a(30) onward from Max Alekseyev, Aug 18 2024

A375433 a(n) is the smallest number of parallel straight lines needed to intersect all points (k, a(k)) for k < n.

Original entry on oeis.org

0, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15

Offset: 1

Rémy Sigrist, Aug 15 2024

nonn

This sequence is a variant of A373811. The two sequences coincide over the first 22 terms.

			See illustration in Links section.

Rémy Sigrist, Table of n, a(n) for n = 1..10000
Rémy Sigrist, Illustration for a(21) = 6
Rémy Sigrist, C++ program

Cf. A373811, A375465.

a(n) <= a(n+1) <= a(n) + 1.

A375465 Lengths of successive runs of equal terms in A375433.

Original entry on oeis.org

1, 2, 3, 3, 5, 4, 4, 6, 6, 5, 5, 5, 10, 6, 7, 6, 6, 6, 6, 6, 13, 9, 7, 7, 8, 7, 7, 7, 7, 7, 7, 7, 18, 11, 8, 10, 8, 8, 8, 9, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 31, 9, 12, 9, 9, 11, 9, 9, 9, 9, 10, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 38

Offset: 1

Rémy Sigrist, Aug 17 2024

nonn

Rémy Sigrist, Table of n, a(n) for n = 1..756

Cf. A373811, A373812, A375433.

A375502 a(n) is the minimal number of parallel straight lines needed to intersect all points (k, prime(k)) for k = 1..n (where prime(k) denotes the k-th prime number).

Original entry on oeis.org

1, 1, 2, 2, 3, 3, 4, 4, 4, 4, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 8, 8, 9, 9, 10, 11, 11, 12, 12, 13, 14, 14, 15, 16, 16, 16, 17, 18, 18, 19, 19, 19, 19, 20, 21, 21, 22, 22, 22, 22, 22, 22, 23, 24, 25, 25, 26, 26, 26, 26, 26, 26, 26, 26

Offset: 1

Rémy Sigrist, Aug 18 2024

nonn

Rémy Sigrist, Table of n, a(n) for n = 1..1000
Rémy Sigrist, PARI program

Cf. A373811, A375433, A373813.

PARI
```
\\ See Links section.
```

A378831 The minimum number of diagonal lines required to cover all vertices created when the n outer vertices of a regular n-gon are connected by diagonal lines.

Original entry on oeis.org

1, 2, 2, 4, 5, 10, 11, 21

Offset: 2

Scott R. Shannon, Dec 08 2024

See A007569 for the total number of vertices created by the diagonal lines of a regular n-gon.
The terms a(9)..a(13) are less than or equal to 21, 25, 38, 41, 59 respectively.
Note that these numbers are not always the same as the minimum number of required lines if the lines can be arbitrarily placed. The first known occurrence where the numbers differ is for a(7) = 10 where one can use eight diagonal lines plus one off-diagonal line to cover two vertices in such a way that all vertices can be covered with only 9 lines.
Better upper bounds for a(10)..a(13) are 23, 36, 38, 56, with a(10), a(11) being almost certainly the correct values. - Scott R. Shannon, Dec 10 2024

Scott R. Shannon, Image showing one example of 11 diagonals covering all 57 vertices of the octagon. The covering diagonals are shown as thicker white lines.

Cf. A007569, A373813, A373811.

a(9) added by Scott R. Shannon, Dec 10 2024

cp's OEIS Frontend

A373812 Lengths of successive runs of equal terms in A373811.

Views

Author

Keywords

Comments

Crossrefs

Extensions

A373813 a(n) is the smallest number of straight lines needed to intersect all points (k, prime(k)) for k = 1..n.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A375499 a(n) is the smallest number of straight lines needed to intersect all points (k, d(k)) for k = 1..n (where d is the sum-of-divisors function A000005).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Extensions

A375433 a(n) is the smallest number of parallel straight lines needed to intersect all points (k, a(k)) for k < n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A375465 Lengths of successive runs of equal terms in A375433.

Views

Author

Keywords

Links

Crossrefs

A375502 a(n) is the minimal number of parallel straight lines needed to intersect all points (k, prime(k)) for k = 1..n (where prime(k) denotes the k-th prime number).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

A378831 The minimum number of diagonal lines required to cover all vertices created when the n outer vertices of a regular n-gon are connected by diagonal lines.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions