[seqfan] A285175; Lexicographically earliest sequence of positive integers such that no k+2 points fall on any polynomial of degree k.

[David Corneth]

Hi all,

Interesting sequence! I've some thoughts on it. First, the sequence is
also:
"Lexicographically earliest sequence of positive integers such that any k+1
points fall on a polynomial of degree k." (I.e. no k+3 points fall on a
polynomial of degree k as well etc.)
(Proof: suppose there are k+3 points that lie on a polynomial of degree k.
Then there are k+2 of those points that lie on a polynomial of degree m
where m <= k. If m < k then throug the k + 3 points goes a polynomial of
eighter degree m or of degree k + 2. Contradiction. If m = k then We have a
contradiction with the definition of this sequence.)

We can find the coefficient via this method:
https://en.wikipedia.org/wiki/Divided_differences)
This way we don't have to compute the entire polynomial through all these
points but just the leading coefficient; the one from the highest power of
n (of the independent variable from the polynomial). If that coefficient is
0 then the degree is too small.

I ran three computations, each starting to check for polynomials 2 points
on a polynomial of degree 0 (a horizontal line), then three points on a
degree 1 polynomial etc. If the candidate-term c lies on such a polynomial,
try c+1 until it's 'good'.

For example, Suppose we're a bit into calculation and we've found the
(actual) data (1, 2, 4, 3, 6, 5). We then try a(7) = 2 (by definition, 1 is
in the sequence) but that has degree less than 2-1 = 1 with the two points
(2, 2) and (7, 2). Similarily, we exclude 3 through 6. Then a(7) = 7 gives
a polynomial of less then 3-1 = 2 through (1,1), (2,2) and (7,7). We
exclude a(7) = 8 because there is a polynomial of degree less then 3-1 = 2
through the 3 points (3, 4), (5, 6) and (7, 8). a(7) = 9 doesn't get
excluded, therefore, a(7) = 9.

The degree of the polynomial can get larger, for example, to exclude a(8) =
12, we need to check that through 6 points (2, 2), (3, 4), (4, 3), (6, 5),
(7, 9) and (8, 12) goes a polynomial of degree less than 6-1 = 5 (actually
of degree 4 as then expected, the polynomial is -11n^4/120 + 23n^3/12 -
329n^2/24 + 481n/12 - 186/5).

Now this might rise the question: What is the highest degree to check for?
I get these results (offset 1), which would make an interesting sequence I
think. I computed somewhat further than terms currently in the sequence and
have terms in brackets conjectured.
Highest degree of polynomial needed (in hindsight) to find a(k)
respectively:
0, 0, 1, 0, 1, 0, 1, 4, 2, 2, 0, 3, 0, 1, 4, 2, 3, 4, 3, 4, 6, 2, 7, 0, 2,
4, (0, 9, 2, 3, 0, 4, (5)) I interrupted the calculation for a(33) early
on, and it had checked upto 5 points for a(33) <= 58 and excluded all
those.

Now I wanted to compare these figures to what would happen if I wouldn't
stop checking points after excluding a candidate-value. For example, though
after checking 1 degree polynomials we can exclude a(7) = 7. If we keep
checking anyway we find that there's another polynome that excludes a(7) =
7; the polynomial through
 (1,1), (3, 4), (5, 6) and (7,7) is of degree less then 4-1 = 3 (i.e. of
degree 2). Doing this up to a(19) gives me
0, 0, 1, 0, 2, 1, 4, 4, 5, 6, 6, 7, 6, 4, 6, 8, 9, 10, 9.

Now, lastly I carried on the computation and have an estimate for a(27)
through a(33). The sequence currently lists 26 terms. From n = 13 onwards I
checked for polynomials up to ceil(n / 2.5) points, including the
candidate. So to estimate a(27), I checked up to k = ceil(27 / 2.5) = 11
points including the candidate. All of 1 through 10 could be falsified. I
didn't find a polynomial of degree less then k through k + 1 points for k <
11.

Now, this is the data I have using
Data assuming highest amount of points to check is ceil(n / 2.5) for 12 <=
n <= 32. For n < 12, check all sets of points.
1, 2, 4, 3, 6, 5, 9, 16, 14, 20, 7, 15, 8, 12, 18, 31, 26, 27, 40, 30, 49,
38, 19, 10, 23, 53, (11, 32, 21, 25, 13, 47, (59)). Assuming a(27) through
a(32) correct, a(33) > 58.
Can these go in the sequence, possibly as a comment saying they're
conjectured?

Now, about the conjecture. I'd guess that it's a permutation of the
positive integers anyway. 11 and 13 didn't occur yet, but occur anyway
(assuming the calculations are correct).

To summarize:
How far must we check to be sure of a found a(n)?
Can we change A285175?
How about sequence listing highest numbers of points to check to find a(n)?


Now a practical question, I have two files including the sets of points
that exclude candidate values. Are they interesting to put up somewhere?
One file lists the first polynomial to exclude (n, m) for 2 <= m < a(n),
the other all the polynomials that exclude terms up to a(19). The first has
572 polynomials, the second (only!) 629, where the first has 227
polynomials for a(19). The file might help to predict through which k+2
points passes a polynomial of degree k, though I don't see how right now.

Any thoughts?
Best,
David