[seqfan] Re: Worry about old sequence, A030077, paths in K_n

[Brendan McKay]

Hi Tim,  I think you are on a good trail.

Please refer to my previous email for the definitions of "admissible"
and "realizable".  It is known that all realizable multisets are admissible
and the BHR conjecture is that admissible=realizable.  That has been
proved up to n=19.  It would be nice to go further.  I guess that the
most expensive multisets to test are those which are not realizable,
but you can eliminate probably all of those by testing for admissibility.

Depending on how you are doing the bookkeeping, you can eliminate
most admissible multisets quickly by making a large number of
random paths.  Then you only need to test the admissible multisets
that have not been spotted.

The next case of BHR is n=20.  There are 6,906,900 multisets, of
which 6,871,780 are admissible.

I have code that has already compared total lengths of all admissible
multisets up to n=25 using exact arithmetic, so the remaining problem
is whether there are admissible multisets that are not realizable.

Best near-misses (for unit circle): 3e-11 for n=22 and 5e-12 for n=23.

Cheers, Brendan.

On 4/4/2022 4:26 pm, Tim Peters wrote:
> Here's a different approach for the front part: forget permutations,
> work directly from weak compositions instead. Despite that I'm using
> plain Python, it was fast enough to do all the following in under 90
> minutes. So far, this confirms the results through a(16) Brendan
> already reported, and adds a(17).
>
> 4 ints per line:
>
> - n
> - the number of weak compositions of n-1 into floor(n/2) parts
>        see OEIS notes for more on that
> - the number of weak compositions that can actually be realized for n
>        this was called the number of distinct multisets in earlier msgs
> - the number of those with unique sums
>
> As before, I'm still doing the last part with native 64-bit floats,
> trusting PSLQ saying there are no non-identity "almost matches" among
> linear combinations of sin(j * pi / n) values for n in this range.
>
> The vast bulk of the time is spent figuring out whether a composition
> can be realized. I don't have a clever way to do that. Instead there's
> a recursive brute-force function that basically tries all ways of
> chaining the n-1 composition segments, starting at point 0. If, along
> the way, all n points are reached, success. Else we reach some
> intermediate step where the next (at most) two possible points have
> already been reached, and so it backtracks there.
>
> 2 1 1 1
> 3 1 1 1
> 4 4 3 3
> 5 5 5 5
> 6 21 17 17
> 7 28 28 28
> 8 120 105 105
> 9 165 161 161
> 10 715 670 670
> 11 1001 1001 1001
> 12 4368 4129 2869
> 13 6188 6188 6188
> 14 27132 26565 26565
> 15 38760 38591 14502
> 16 170544 167898 167898
> 17 245157 245157 245157