[seqfan] Fwd: Worry about old sequence, A030077, paths in K_n
Brendan McKay
Brendan.McKay at anu.edu.au
Sat Apr 2 15:51:09 CEST 2022
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.
More information about the SeqFan
mailing list