[seqfan] Re: Stepping stones puzzle, A337663

[Neil Sloane]

Robert,  that is really amazing, I did not think it was possible by that
approach.
Congratulations!

I see the general idea, but I got lost around the point where you mentioned
A, B, and W.  When you have time, could you give details starting at that
point?

Best regards
Neil

Neil J. A. Sloane, Chairman, OEIS Foundation.
Also Visiting Scientist, Math. Dept., Rutgers University,
Email: njasloane at gmail.com



On Wed, Oct 5, 2022 at 3:15 PM Robert Gerbicz <robert.gerbicz at gmail.com>
wrote:

> 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.
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>