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.

1, 1, 1, 3, 5, 17, 28, 105, 161, 670, 1001, 2869, 6188, 26565, 14502, 167898, 245157, 445507, 1562275, 6055315, 2571120, 44247137, 64512240, 65610820, 362592230, 1850988412, 591652989, 11453679146, 17620076360, 1511122441, 114955808528, 511647729284, 67876359922, 3347789809236, 1882352047787, 1404030562068, 32308782859535

Offset: 1

Author

Daniel Lurie Gittelson, Dec 11 1999

Keywords

• nonn
• nice

Comments

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]

Examples

			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)).
For n=5, the 4 edges of the path may include 0,...,4 diagonals, so a(5)=5.
		

Links

• Samuel C. Gutekunst, Circulant TSP: Vertices of the Edge-Length Polytope and Superpolynomial Lower Bounds, arXiv:2506.10758 [cs.DM], 2025. See pp. 2-3, 17-18.
• Sean A. Irvine, Java program (github)
• Brendan D. McKay and Tim Peters, Paths through equally spaced points on a circle, arXiv:2205.06004 [math.CO], 2022.

Crossrefs

Cf. A007874 (similar, but with n line segments), A052558, A099578.

See A352568 for the multisets of line lengths.

Extensions

a(13) - a(16) from T. D. Noe, Jan 09 2007

Removed unnecessary mention of dihedral group from definition. - N. J. A. Sloane, Apr 02 2022

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

a(17) to a(37) from Brendan McKay, May 14 2022