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

Brendan McKay Brendan.McKay at anu.edu.au
Sun Apr 3 03:57:07 CEST 2022

```It took 4.7 hours to do n=16.  There are 167898 distinct multisets of
edge lengths, and no two of them are closer than 10^{-7} in total
length.  So the value in the existing A052558 entry is correct.

Thus, I believe all the values in the entry are correct.  The reason the
graph looks dubious is that only for some values can distinct multisets
have the same total.  For n <= 16, this happens only for 12 and 15.

The number of distinct multisets of edge lengths up to n=16 is
1, 1, 1, 3, 5, 17, 28, 105, 161, 670, 1001, 4129, 6188, 26565, 38591,
167898,
which is not in OEIS.

Now I will run n=17.

Brendan.

On 3/4/2022 12:51 am, Brendan McKay via SeqFan wrote:
> Dear Seqfans,
>
> The values are correct up to 15 points (800 seconds cpu).
> n=16 will run overnight, and I will do 17 too but it might take a week.
> My method is exact, with no guesswork about approximate arithmetic.
>
> I trace all paths (limited by fixed starting point and direction to go
> first).
> As I do that, I collect which multisets of edge lengths occur, the number
> of which is not in OEIS but should be.
>
> Then I sort the multisets by their length calculated with 19-digit
> arithmetic.
> Lengths whose approximation differs by 10^{-7} (using the unit circle)
> or more can't possibly be equal.  (That's a rigorous fact.)
>
> That leaves some collections of multisets whose approximations differ by
> less than 10^{-17}.  So far no differences between 10^{-17} and 10^{-7}
> have appeared.  For all those probably-equal lengths, Maple's simplify( )
> function manages to show they are exactly equal.
>
> I figured out where the dihedral group comes in.  It is relevant to
> the comment
> "there are A052558(n-2) paths to be considered"  since A052558(n-2)
> counts
> equivalence classes of directed hamiltonian paths under the dihedral
> group.
> It isn't quite correct that only that many paths need considering,
> since almost
> another factor of 2 could be achieved by considering the reverse of
> the path
> (but I'm not using that).
>
> For some reason I only see a fraction of seqfan postings, so please CC me
> on anything you want me to see.
>
> Cheers, Brendan.
>
>
> --
> Seqfan Mailing list -