OFFSET
1,3
COMMENTS
Let PrimePoint(k) denote the point in the plane with coordinates x=k, y=prime(k). Then a(n) is the minimal number of straight lines needed to cover the points PrimePoint(1) through PrimePoint(n).
Note that the /set/ of a(n) lines that can be used is rarely unique.
Each line can be specified by two numbers i and s, and denoted by i$s, indicating that the line begins at PrimePoint(i) and has slope s (which may be a fraction) - see EXAMPLES below.
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
LINKS
Jesper Gran Mikkelsen, Table of n, a(n) for n = 1..1024 (first 861 terms from Max Alekseyev)
Max Alekseyev, Sage program for lines covering points, GitHub, Aug 19 2024.
Max Alekseyev, The main table of lines. For each run of equal values of the sequence a(n), 9 <= n <= 861, gives a minimal set of a(n) lines for the start of the run, and a minimal set of a(n) lines for the end of the run. See the "Explanation of format" link for further information.
Brady Haran and N. J. A. Sloane, Awkward Primes, YouTube Numberphile video, 2026.
Scott Duke Kominers, Rudi Mrazović, Carl Pomerance, and Patrick Solé, Lines in the Prime Number Graph, preprint, Dartmouth College (2026). See pp. 2-3, 7.
Jesper Gran Mikkelsen, Full solver output for n = 1..1024, including per-step statistics and optimal cover lines
Jesper Gran Mikkelsen, Prime Line Cover solver, GitHub.
Jesper Gran Mikkelsen, Interactive demo (JavaScript port of the solver, runs in browser).
Jesper Gran Mikkelsen, An Exact Solver for the Minimum Line Cover of Prime-Indexed Points, preprint, 2026.
Jesper Gran Mikkelsen, Source code and certified results for n = 1..1024, Zenodo, 2026.
N. J. A. Sloane, A minimal set of lines for all primes <= 97, extracted from the Main Table, using the same notation
N. J. A. Sloane, Illustration for a(9)=3.
N. J. A. Sloane, Explanation of format used in Main Table. Gives as an example an explanation for the entry "A373813 : 9 3" in the Main Table.
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]
Ruud H.G. van Tol, Picture of a(5) (svg), generated with these commands.
EXAMPLE
Notation: i$s denotes the line starting at the point PrimePoint(i) = (i, prime(i)) and having slope s. Take only PrimePoints(j) with j <= n.
n a(n) Lines
1 1
2 1 1$1 1$1 is the line [(1,2), (2,3)]
3 2 1$1, 2$2 2$2 is the line [(2,3), (3,5), (4,7)]
4 2 1$1, 2$2
5 2 1$9/4, 2$2 1$9/4 is the line [(1,2), (5,11)]
6 3 1$9/4, 2$2, 5$2
7 3 1$9/4, 2$2, 6$4
8 3 1$1, 3$3, 4$3 3$3 is the line [(3,5), (5,11), (7,17)]
9 3 1$1, 3$3, 4$3 4$3 is the line [(4,7), (6,13), (8,19)] (See link)
10 4 1$9/4, 2.2, 6$4, 8$4
11 4 1$9/4, 2.2, 6$4, 8$4
12 4 1$9/4, 2.2, 6$4, 8$4
PROG
(C++) // See Links
CROSSREFS
KEYWORD
nonn,nice,changed
AUTHOR
Rémy Sigrist and N. J. A. Sloane, Aug 18 2024
EXTENSIONS
Terms a(19) to a(410) from Max Alekseyev, Aug 18 2024
Edited by N. J. A. Sloane, Mar 10 2026
STATUS
approved