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

Neil Sloane njasloane at gmail.com
Sun Apr 3 06:09:35 CEST 2022

```I created A352568 for the number of multisets version.  Feel free to edit
it.

Brendan, would you be willing to add your program to A030077 as a .txt
file?  As Antti just pointed out, we have had a lot of problems over the
years because people did not post their programs.  Antti says, and I agree,
for the initial computation of a sequence, beauty is irrelevant.  We just
want to know how the numbers were computed.  We don't care much if the
program is ugly. Chances are no one will run it, but we do need to have it
on record just in case.

This is the same situation as with the first proof of a theorem.  If the
proof is elegant, so much the better. But all that really matters is that
it must be correct.

together some comments for the record, along the lines of the postings you
both recently made?  This could be another .txt file.

Best regards
Neil

Neil J. A. Sloane, Chairman, OEIS Foundation.
Also Visiting Scientist, Math. Dept., Rutgers University,
Email: njasloane at gmail.com

On Sat, Apr 2, 2022 at 11:04 PM Brendan McKay via SeqFan <
seqfan at list.seqfan.eu> wrote:

> Another point on this.  Consider three sequences:
>
> 1  2  3  4  5   6   7   8    9   10    11    12    13     14     15
> 16 1, 1, 1, 3, 5, 17, 28, 105, 161, 670, 1001, 2869, 6188, 26565, 14502,
> 167898 1, 1, 1, 3, 5, 17, 28, 105, 161, 670, 1001, 4129, 6188, 26565,
> 38591, 167898    1, 1, 4, 5, 21, 28, 120, 165, 715, 1001, 4368, 6188,
> 27132, 38760, 170544
>
> In order:
> A030077(n) distinct lengths, distinct multisets, A099578(n-2) binomial
> coeff.
>
> The comment in A030077 (Noe, edited by Hadjicostas) says
>     "an upper bound for a(n) is the number of compositions of n-1 into
> floor(n/2)
>     nonnegative parts, which is A099578(n-2). It appears that the upper
>     bound is attained for prime n."
>
> I don't think "it appears" counts for much and I propose this last sentence
> be removed or restated more clearly as a conjecture.
>
> Robert Gerbicz showed us recently that distinct multisets have distinct
> lengths in the prime case, but it remains to be shown that all multisets
> can be achieved in the prime case.  If n is not prime and k is a proper
> divisor of n,  then the multisets with every element a multiple of k are
> not achieved.  (First case: 3 diagonals for n=4.)
>
> Brendan.
>
> On 3/4/2022 11:57 am, Brendan McKay via SeqFan wrote:
> > 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 -
> >>
> >
> > --
> > Seqfan Mailing list -
> >