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

[Sean A. Irvine]

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/
>