[seqfan] Stepping stones puzzle, A337663

[Robert Gerbicz]

Liminf a(n)/n>6 !
Breakthrough, btw my old result, just not posted. Posting before I forget
the construction, giving also a code to convince myself that the
construction is really good.

Proving with a little lengthy explicit construction, for every n:
a(n)>6.0128*n-5621

Proof:
Of course a(n) is an increasing sequence, for m>n the a(m)>=a(n), use the
construction for n, and place the m-n additional ones that has no neighbour
with numbers from [2,a(n)].

Showing that
a(934*t+528)>=5616*t+3164 for every integer t>=0, and from the increasing
condition it follows that:
a(n)>=(2808*n-2624900)/467  so a(n)>6.0128*n-5621

Start with the basic 6n-1 construction:

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

Call this just a tree (or house in the code).
The first idea is that we can build (main) branches on this:

   9
 8 1 10
 7   11 33 34 35 36 37 38 39 40 41
 6   12        1        1        1 42
 5 1 13    50 49 48 47 46 45 44 43
 4   14
 3   15
 2 1 16
 1   17
(it is not a construction for n=50, just showing how to place the interval
[33,50]).

 We would still be at the level with this, since with p additional ones we
can place 6p numbers.
In some cases it is better to push down almost the whole branch:
   9
 8 1 10
 7   11 33
 6   12    34 35 36 37 38 39 40 41
 5 1 13        1        1        1 42
 4   14    50 49 48 47 46 45 44 43
 3   15
 2 1 16
 1   17

Notice we can not start with every number these branches, since in general:
t
t+1 3t+3
t+2

So we can start only with a number that is divisible by 3.
If somehow we could freely place (without using more ones) 3 consecutive
numbers, then
just start a branch at t+2 instead of t+1 and saved a "half" one.

And this works, use the places marked at A,B and W.

   9
 8 1 10
 7   11 33
 6   12    34 35 36 37 38 39 40 41  A
 5 1 13     W  1        1        1 42
 4   14    50 49 48 47 46 45 44 43  B
 3   15
 2 1 16
 1   17
 (and you can see why it is pushed down the branch, otherwise 33 would be
also included in the sum for W).

Why is it good? Because even these are of course not 3 consecutive numbers.
But gives a complete residue system mod 3, it is also true that B=A+2, but
it isn't interesting. Drawing enough const*n branches, we will see const*n
such a full residue system. Hence giving a (6+c)*n construction for fixed
c>0. At W the number is larger than A or B, but it is not a problem, we can
use that independently from A,B.

It is almost good. Since A,B,W are too large, we needed also to build
branches on the main branches. And also a little complication because on
the (main) branch we would need to find 6 consecutive numbers and not
three(!) that we could place freely. To avoid this use also this ladder
construction between the main branches:

(The numbers marked with x are on the branch.)
xxxxxxxxxxxxxxxx
        h
        h+1
  g+8 1 h+2
  g+7   h+3
  g+6   h+4
  g+5 1 h+5
  g+4   h+6
  g+3   h+7
  g+2 1 h+8
  g+1
  g
xxxxxxxxxxxxxxx

(yes, we could also freely place g+9 and h+9, but it is not used).

To get a solution for n=934*t+528 call the code with t (without any
switch). Do not use line breaking in the file to see the construction.
The grid is checked, and also printed out the values, coordinates to
another file.