[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, 
which is not in OEIS.

Now I will run n=17.


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 - 
> https://aus01.safelinks.protection.outlook.com/?url=http%3A%2F%2Flist.seqfan.eu%2F&data=04%7C01%7Cbrendan.mckay%40anu.edu.au%7C1c7e6bdf0ff0480b779608da14afdf3a%7Ce37d725cab5c46249ae5f0533e486437%7C0%7C0%7C637845043162296854%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=kacZA%2FgY04c3Jv%2FRsuvMTCaF%2BCVWOL2Sm1EUoLELX0s%3D&reserved=0

More information about the SeqFan mailing list