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