[seqfan] Re: Stepping stones puzzle, A337663
Robert Gerbicz
robert.gerbicz at gmail.com
Fri Oct 7 01:54:48 CEST 2022
OK, but it was not my intention to give a very strict proof with all
computed constants, just to show the ideas. Say, really not proved that it
is giving n=934*t+528, just calculated it from two t values, assuming that
n is linear in t.
For the input t number: p=156t+97 and the given construction will show that
a(934*t+528)>=5616*t+3164
So first use the basic construction using p ones (house/tree construction),
an additional one to place down 6p,6p+1,6p+2. Really don't know why we
needed these 3 extra numbers.
What I have not said, but it is clear from the generated construction that
the (horizontal) main branches contain an equal number of ones, that is
H=13. This also means that 6H numbers (bigger than 1) are on each main
branch. And the distance of these consecutive main branches is also
constant, 6*H/3=26.
Then the first missing number is 6p+3, so the first main branch starts at
6p+3.
The k-th main branch starts at 6p+78k+3. Easily:
A=12p+156k+84, B=A+2, W=24p+312k+169.
If for k=k' at W we would see A+1=W then we have 3 consecutive numbers
A,W,B.
A+1=W gives that:
12*p+156*k+84+1=24*p+312*k'+169
solving for k' gives k'=(-12*p+156*k-84)/312
it turns out that if for example p=97 mod 156 and k is even then k' is an
integer.
For A,W,B it is not used additional ones, so for each such triple saving a
half one over the classical 6m construction, if we can place down linear
number of triplets, and that is the case, notice that (roughly):
12p<A,B<36p and 24p<W<72p
So there will be a solution if 24p<A,B,W<36p, it means const*p=const*n
saved ones.
Why we need the ladder construction, see for example on the construction
you have [10,19] placed, and 33,34,35 and 51 52 53 is already placed:
10 11 12 13 14 15 16 17 18 19
You would need to place [36,50] (using also the [10,19] numbers), but that
is 15 consecutive numbers and we can place only 6m numbers with m ones, or
if we'd lost a half one, but then we would be again at level on the 6m
construction. The solution is to use that ladder that contains numbers from
2 intervals, and not from one interval.
The vertical branches are periodic with 8 consecutive horizontal main
branches if you're placing the W, the heights are in the large W array.
Before that the period is 1 (and the heights are in the U array), so a much
easier form, since there is no missing triplet.
ps. As you can see we won't use all possible W numbers, some of them are
missing, the reason is that in some cases it would give 3 consecutive
numbers that we simply can't handle that case even with a ladder.
Neil Sloane <njasloane at gmail.com> ezt írta (időpont: 2022. okt. 6., Cs,
6:41):
> 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/
> >
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>
More information about the SeqFan
mailing list