## Sunday, October 13, 2013

### PyramidSequences

First, fix some $$n$$ and $$m$$. We begin by looking at an easier problem: If instead of looking at sequences of the form $$1, 2, \ldots, n - 1, n, n - 1, \ldots, 3, 2$$, what if all the sequence elements were distinct (e.g. if the sequence was of the form $$1, 2, \ldots, 2 n - 2$$)? The Chinese remainder theorem guarantees that a number $$x$$ from the $$n$$-sequence will be paired with a number $$y$$ from the $$m$$-sequence if and only if $$x \equiv y \pmod{2g}$$, where $$g = \gcd( n - 1, m - 1 )$$. We can partition the $$n$$- and $$m$$-sequences into equivalence classes modulo $$2g$$; each class contains $$(n - 1) / g$$ or $$(m - 1) / g$$ elements, so there are $$(n - 1) (m - 1) / g^2$$ pairings per class, or $$(n - 1) (m - 1) / g^2$$, or $$2 (n - 1) (m - 1) / g$$ unique pairings.

Unfortunately, the pairings are not unique. Each $$k$$ in the $$n$$-sequence has two possible indices modulo $$2 g$$: $$\{ k \% (2 g)$$ and $$(2 n - k) \% (2 g) \}$$. Let us first consider the two indices are equal, i.e. $$k \equiv (2 n - k) \pmod{2g}$$. Simplifying, this gives us $$k \equiv n \pmod g$$. Since $$g$$ is a multiple of $$n - 1$$, then $$n \equiv 1 \pmod g$$, so our final expression is $$k \equiv 1 \pmod g$$; i.e. $$k \equiv 1 \text{ or } g + 1 \pmod{2g}$$. Note that this condition is independent of $$n$$ or $$m$$, so it suffices to simply find the number of $$k$$ equivalent to $$1$$ or $$g + 1$$ modulo $$2g$$ in each sequence and multiply the counts accordingly.

Now consider the case in which $$k$$ has two distinct indices, $$k \% (2 g)$$ and $$(2 n - k) \% (2 g)$$. Again, since $$n \equiv 1 \pmod g$$, the second index can be written $$(2 - k) \% (2 g)$$. If $$k \% (2 g) \in [2, g]$$, then $$(2 - k) \% (2 g) \in [g + 2, 2g]$$ and vice versa. Thus, each $$k$$ appears exactly once in the range $$[2, g]$$ and exactly once in $$[g + 2, 2g]$$. It suffices, then, to compute the result for one range. This is simply $$(g - 1) (n - 1) (m - 1) / g^2$$.

Putting the two cases ($$k \equiv 1 \pmod g$$ or not) together, we have the following Python code. Some care must be taken to account for the special cases $$1$$, $$n$$, and $$m$$.

from fractions import *

class PyramidSequences(object):
def distinctPairs(self, n, m):
g = gcd(n - 1, m - 1)
an, am = [(x - 1) / g for x in n, m]
bn, bm = [x / 2 + 1 for x in [an, am]]
cn, cm = [x / 2 + (x % 2) for x in [an, am]]
return (g - 1) * an * am + bn * bm + cn * cm