[seqfan] Re: Probable mistake in A013582 (number of states in Connect-4).

[Sean A. Irvine]

And published.

On Mon, 5 Dec 2022 at 09:33, Sidney Cadot <sidney at jigsaw.nl> wrote:

> Great. I have uploaded a corrected b-file and made an edit to reflect the
> corrected value.
>
> Thanks, Sidney
>
> On Sun, Dec 4, 2022 at 12:15 AM Sean A. Irvine <sairvin at gmail.com> wrote:
>
>> Hi Sidney,
>>
>> Great news, you are indeed correct.  It looks like I simply forgot to
>> divide by 2 in the last entry!
>>
>> I found the outputs from my runs. It looks like what I actually did was
>> generate all symmetric configurations (or perhaps those that could lead to
>> symmetric configurations). The timestamps on those files indicate that it
>> was run 1 Oct 2018 to 3 Oct 2018. So "only" a couple of days to generate
>> all the data because it was a much smaller set of states needed.  Then I
>> computed A013582 from the known numbers for A212693 and the count of
>> symmetric cases.
>>
>>  The file for n=42 contains 43199 lines (matching the s(n) number in the
>> table I sent before).  I should have computed (1459332899+43199)/2 =
>> 729688049, but it seems I simply forgot to divide by 2.  When I mailed you
>> earlier, I was looking at s(n) and thinking it all looked reasonable, but I
>> did not think to check that I had done the arithmetic step right.
>>
>> Please go ahead and propose a correction in the OEIS (I or another editor
>> can then approve).
>>
>> Sean.
>>
>> On Sun, 4 Dec 2022 at 09:20, Neil Sloane <njasloane at gmail.com> wrote:
>>
>>> Sean,  you might keep Russ in the loop, since it was his sequence
>>>
>>> Best regards
>>> Neil
>>>
>>> Neil J. A. Sloane, Chairman, OEIS Foundation.
>>> Also Visiting Scientist, Math. Dept., Rutgers University,
>>> Email: njasloane at gmail.com
>>>
>>>
>>>
>>> On Sat, Dec 3, 2022 at 2:51 PM Sean A. Irvine <sairvin at gmail.com> wrote:
>>>
>>> > Hi Sidney,
>>> >
>>> > You make a plausible case that my existing value for A013582(42) is
>>> wrong.
>>> >
>>> > I'll follow up with you in more detail off the list and we can post
>>> back a
>>> > summary later when it is resolved.
>>> >
>>> > Sean.
>>> >
>>> >
>>> > On Sun, 4 Dec 2022 at 04:49, Sidney Cadot <sidney at jigsaw.nl> wrote:
>>> >
>>> > > Hi all,
>>> > >
>>> > > Recently I have completed brute-forcing the game of Connect-4 using a
>>> > > self-written program.
>>> > >
>>> > > OEIS contains two relevant sequences concerning the number of
>>> positions
>>> > > after *n* plies:
>>> > >
>>> > > A013582 - total number of positions after *n* plies, up to
>>> reflection;
>>> > > A212693 - total number of positions after *n* plies.
>>> > >
>>> > > My solver agrees fully with A212693, and with A013582 on all but the
>>> last
>>> > > value. Currently, OEIS says A013582(42) = 1459376098; however, the
>>> > solution
>>> > > I found suggests that this value should be 729688049.
>>> > >
>>> > > Note that this value is precisely half the value currently given in
>>> > A013582
>>> > > on OEIS.
>>> > >
>>> > > It is quite hard to reproduce this calculation (a dedicated computer
>>> > worked
>>> > > for about 6 months to traverse the whole game DAG twice, producing
>>> some
>>> > 15
>>> > > TB of data in the process), so another line of reasoning is more
>>> useful
>>> > to
>>> > > assess my claim that the currently listed value is not correct.
>>> > >
>>> > > Here is such an argument:
>>> > >
>>> > > In general, we find that 2 * A013582(n) is slightly larger than
>>> > A212693(n).
>>> > > This is to be expected, as most boards by far are not their own
>>> mirror
>>> > > image, but some are.
>>> > >
>>> > > In fact, we can calculate the number of horizontally *symmetrical
>>> *boards
>>> > > after n plies as 2 * A013582(n) - A212693(n), and the total number of
>>> > > *nonsymmetric
>>> > > *boards as A212693(n) - ( 2 * A013582(n) - A212693(n)) = 2 *
>>> (A212693(n)
>>> > -
>>> > > A013582(n)).
>>> > >
>>> > > Assuming both the numbers A212693(42) = 1459332899 and A013582(42) =
>>> > > 1459376098 currently in OEIS are correct, we can calculate the
>>> number of
>>> > > non-symmetrical full boards as:
>>> > >
>>> > > 2 * (1459332899 - 1459376098) = -86398
>>> > >
>>> > > The actual number of non-symmetrical full boards cannot, of course,
>>> be
>>> > > negative. We can therefore conclude that the assumption that
>>> A212693(42)
>>> > > and A013582(42) are both correct must be false. Following my solver,
>>> I
>>> > > think that this is because the last value of A013582 as currently
>>> listed
>>> > is
>>> > > off by a factor of two.
>>> > >
>>> > > My question to the readers: could you review my argument and if you
>>> > agree,
>>> > > make a correction to A013582?
>>> > >
>>> > > With kind regards,
>>> > >
>>> > >   Sidney Cadot
>>> > >
>>> > > --
>>> > > Seqfan Mailing list - http://list.seqfan.eu/
>>> > >
>>> >
>>> > --
>>> > Seqfan Mailing list - http://list.seqfan.eu/
>>> >
>>>
>>> --
>>> Seqfan Mailing list - http://list.seqfan.eu/
>>>
>>