[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