A381194 Number of equal-length matchings of 2n uniformly spaced points on a circle.

1, 3, 3, 9, 5, 17, 7, 33, 15, 49, 11, 113, 13, 153, 57, 321, 17, 617, 19, 1153, 165, 2089, 23, 4577, 85, 8241, 555, 16737, 29, 34049, 31, 66177, 2109, 131137, 377, 267521, 37, 524361, 8265, 1051393, 41, 2114081, 43, 4198561, 33945, 8388697, 47, 16851905, 427, 33556689

Offset

1,2

Comments

a(n) is the number of ways to draw n segments of equal length so that each vertex of a regular 2n-gon is an endpoint of one of the segments. It is not difficult to prove that the Maple program given below computes the correct value. Note that a(n) = n when n is an odd prime.

Finding the value when n = 12 was a problem in the 2025 American Invitational Mathematics Examination (AIME), a part of the American Mathematics Competitions run by the Mathematical Association of America. A solution is presented in the Art of Problem Solving website.

Links

Yifan Xie, Table of n, a(n) for n = 1..5000

Art of Problem Solving, 2025 AIME II Problems/Problem 11.

Formula

a(n) = 1 + Sum_{i=1..n-1} [2*n/GCD(2*n,i) mod 2 == 0] * 2^GCD(2*n,i), where [ ] denotes the Iverson bracket.

Maple

a := 1;
for i from 1 to n - 1 do
    if (2*n/gcd(2*n, i)) mod 2 = 0 then a := a + 2^gcd(2*n, i); end if;
end do;

Mathematica

a[n_]:=1+Sum[Boole[Mod[2n/GCD[2n, i], 2]==0]2^GCD[2n, i], {i, n-1}]; Array[a, 50] (* Stefano Spezia, Feb 24 2025 *)

Prog

(PARI) a(n)={my(s=1); for(i=1, n-1, my(d=gcd(2*n, i)); if((2*n/d)%2 == 0, s += 2^d)); s} \\ Yifan Xie, Apr 13 2025

Crossrefs

Sequence in context: A104195 A294178 A062131 * A199663 A124871 A197414

Adjacent sequences: A381191 A381192 A381193 * A381195 A381196 A381197

Keyword

nonn

Author

Jerrold Grossman, Feb 16 2025

Status

approved