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

[Sidney Cadot]

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