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

Tim Peters tim.peters at gmail.com
Sat Apr 2 06:51:54 CEST 2022

Here's mindless code that just computes all distance sums, sorts them
to get near-duplicates close together, and then counts the latter as
"the same" if they're within n ulp of each other (using 64-bit binary
floating point here, nothing fancy).

The only "cleverness" is using (n-1)! point permutations instead of
n!, exploiting the obvious symmetry that it doesn't matter which point
comes first.

More cleverness and/or a faster language (than Python) would be needed
to finish this in reasonable time. While typing this up, it managed to
verify the original terms, but now I'm waiting for the first (a(13))
of the last 4 terms ... which matches what OEIS says:

2 1
3 1
4 3
5 5
6 17
7 28
8 105
9 161
10 670
11 1001
12 2869
13 6188

That's the output so far. It will take about 13x longer to get a(14),
and I'm giving up on this approach :-)

FWIW, here's the code:

def drive(n):
    from itertools import permutations
    from math import sin, cos, pi, dist, ulp
    xys = [(cos(ka), sin(ka)) for k in range(n)
           for ka in [k * 2.0 * pi / n]]
    d = set()
    for t in permutations(range(1, n)):
        t = (0,) + t
        ddd = 0.0
        for i in range(n-1):
            ddd += dist(xys[t[i]], xys[t[i+1]])
    count = base = 0
    for x in sorted(d):
        if (x - base)/ulp(base) > n:
            base = x
            count += 1
    return count

for i in range(1, 17):
    print(i, drive(i))

On Fri, Apr 1, 2022 at 10:22 PM Neil Sloane <njasloane at gmail.com> wrote:
> To Seq Fans, The creator of an interesting sequence,  A030077, Daniel
> Gittelson, submitted 12 terms in 1999, and 4 more terms were added in 2007
> by a former editor. Daniel G. wrote to me today, expressing doubt about the
> 4 additional terms.
> He says he interrupted his study of sequences to pursue a medical career,
> but now that he is retired, he can return to combinatorics.
> It would be nice if someone could verify the terms! (It is not at all
> obvious to me how to do this.)
> Neil Sloane
> --
> Seqfan Mailing list - http://list.seqfan.eu/

More information about the SeqFan mailing list