cp's OEIS Frontend

A030077 Take n equally spaced points on circle, connect them by a path with n-1 line segments; sequence gives number of distinct path lengths.

%I A030077 #47 Jun 20 2025 10:46:52
%S A030077 1,1,1,3,5,17,28,105,161,670,1001,2869,6188,26565,14502,167898,245157,
%T A030077 445507,1562275,6055315,2571120,44247137,64512240,65610820,362592230,
%U A030077 1850988412,591652989,11453679146,17620076360,1511122441,114955808528,511647729284,67876359922,3347789809236,1882352047787,1404030562068,32308782859535
%N A030077 Take n equally spaced points on circle, connect them by a path with n-1 line segments; sequence gives number of distinct path lengths.
%C A030077 For n points on a circle, there are floor(n/2) distinct line segment lengths. Hence 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). Conjecture: the upper bound is attained if n is prime. There are A052558(n-2) paths to be considered. - _T. D. Noe_, Jan 09 2007 [Edited by _Petros Hadjicostas_, Jul 19 2018]
%H A030077 Samuel C. Gutekunst, <a href="https://arxiv.org/abs/2506.10758">Circulant TSP: Vertices of the Edge-Length Polytope and Superpolynomial Lower Bounds</a>, arXiv:2506.10758 [cs.DM], 2025. See pp. 2-3, 17-18.
%H A030077 Sean A. Irvine, <a href="https://github.com/archmageirvine/joeis/blob/master/src/irvine/oeis/a030/A030077.java">Java program</a> (github)
%H A030077 Brendan D. McKay and Tim Peters, <a href="https://arxiv.org/abs/2205.06004">Paths through equally spaced points on a circle</a>, arXiv:2205.06004 [math.CO], 2022.
%e A030077 For n=4 the 3 lengths are: 3 boundary edges (length 3), edge-diagonal-edge (2 + sqrt(2)) and diagonal-edge-diagonal (1 + 2*sqrt(2)).
%e A030077 For n=5, the 4 edges of the path may include 0,...,4 diagonals, so a(5)=5.
%Y A030077 Cf. A007874 (similar, but with n line segments), A052558, A099578.
%Y A030077 See A352568 for the multisets of line lengths.
%K A030077 nonn,nice
%O A030077 1,4
%A A030077 _Daniel Lurie Gittelson_, Dec 11 1999
%E A030077 a(13) - a(16) from _T. D. Noe_, Jan 09 2007
%E A030077 Removed unnecessary mention of dihedral group from definition. - _N. J. A. Sloane_, Apr 02 2022
%E A030077 The terms a(1) to a(15) have been verified by _Sean A. Irvine_ and a(1) to a(16) by _Brendan McKay_. - _N. J. A. Sloane_, Apr 02 2022
%E A030077 a(17) to a(37) from _Brendan McKay_, May 14 2022