[seqfan] Re: Worry about old sequence, A030077, paths in K_n
Tim Peters
tim.peters at gmail.com
Mon Apr 4 08:26:42 CEST 2022
Here's a different approach for the front part: forget permutations,
work directly from weak compositions instead. Despite that I'm using
plain Python, it was fast enough to do all the following in under 90
minutes. So far, this confirms the results through a(16) Brendan
already reported, and adds a(17).
4 ints per line:
- n
- the number of weak compositions of n-1 into floor(n/2) parts
see OEIS notes for more on that
- the number of weak compositions that can actually be realized for n
this was called the number of distinct multisets in earlier msgs
- the number of those with unique sums
As before, I'm still doing the last part with native 64-bit floats,
trusting PSLQ saying there are no non-identity "almost matches" among
linear combinations of sin(j * pi / n) values for n in this range.
The vast bulk of the time is spent figuring out whether a composition
can be realized. I don't have a clever way to do that. Instead there's
a recursive brute-force function that basically tries all ways of
chaining the n-1 composition segments, starting at point 0. If, along
the way, all n points are reached, success. Else we reach some
intermediate step where the next (at most) two possible points have
already been reached, and so it backtracks there.
2 1 1 1
3 1 1 1
4 4 3 3
5 5 5 5
6 21 17 17
7 28 28 28
8 120 105 105
9 165 161 161
10 715 670 670
11 1001 1001 1001
12 4368 4129 2869
13 6188 6188 6188
14 27132 26565 26565
15 38760 38591 14502
16 170544 167898 167898
17 245157 245157 245157
More information about the SeqFan
mailing list