This week’s Fiddler is a problem about a multi-sided Möbius prism:
Consider an three-dimensional prism whose bases are regular N-gons. I twist it and stretch it into a loop, before finally connecting the two bases. Suppose that my twist is by a random angle, such that the two bases are aligned when they are coonected. Among all whole number values of N less than or equal to 1,000, for which value of N will a randomly twisted regular N-gon prism have the most distinct faces, on average?
My solution:
[Show Solution]
Label the faces $\{1,2\dots,N\}$, and suppose we apply a twist of $k/N$ before connecting the bases together. We only need to consider $k\in\{1,\dots,N\}$ since adding any multiple of $N$ just adds a full rotation and changes nothing. In other words, rotating by $N$ is the same as not rotating at all.
To count the number of faces in the final shape, we can start from any face and follow that face around until we end up back where we started. Call this an “orbit”. All the numbered faces we cross along the way in a given orbit are in fact the same face, so the total number of faces is just the total number of orbits. By symmetry, each orbit has the same length, so we have:
\[
\text{#(faces)} = \text{#(orbits)} = \frac{N}{\text{(orbit length)}}
\]To find the orbit length, we can write a repeating list of all the faces, and then jump in steps of length $k$ until we end up at a multiple of $N$, which means we have returned to our starting point. In the example below, we have $N=6$ and $k=4$.
\[
\begin{array}{|cccccc|cccccc|cccc}
1 & 2 & 3 & \fbox{4} & 5 & 6 & 1 & \fbox{2} & 3 & 4 & 5 & \fbox{6} & 1 & 2 & 3 & \cdots \\
\end{array}
\]Therefore, as we orbit, we pass through $4 \to 2 \to 6 \to 4 \to \cdots$. This means that the faces $\{2,4,6\}$ in the original prism all belong to the same face in the Möbius prism. This orbit has length $3$, and by symmetry, all other orbits have length 3. Indeed, there is one other orbit: $\{1,3,5\}$. So two total orbits, and therefore two total faces. Based on the illustration above, it’s clear that the least common multiple (lcm) of $N$ and $k$ gives us the point where we return to the face labeled $N$. We can divide this by $k$ to find the length of the orbit:
\[
\text{(orbit length)} = \frac{\text{lcm}(N,k)}{k}
\]Substituting this into our previous equation, we have:
\[
\text{#(faces)} = \frac{N}{\text{(orbit length)}}
= \frac{N \cdot k}{\text{lcm}(N,k)}
= \text{gcd}(N,k)
\]where gcd is the greatest common divisor. In the last line, we used the fact that $\text{lcm}(m,n)\cdot\text{gcd}(m,n) = m \cdot n$. For the example above with $N=6$ and $k=4$, we have $\text{gcd}(6,4) = 2$, and indeed there are two orbits (and therefore, two faces).
The problem asks to find the average number of faces assuming the twist is random. Let’s call this quantity $f(N)$. Based on what we found so far, we have:
\[
f(N) = \frac{1}{N}\sum_{k=1}^{N} \text{gcd}(N,k)
\]The sum of gcd’s of a number is known as Pillai’s arithmetical function (OEIS A018804), and there are alternative formulas for it. One such formula is found by writing $N = p_1^{a_1}\cdots p_m^{a_m}$ (prime factorization), and then it turns out that:
\[
f(N) = \frac{1}{N}\prod_{i=1}^m\left( (a_i+1)p_i^{a_i}-a_i p_i^{a_i-1} \right)
\]This is still a complicated function, so we turn to a computer to evaluate it for $1 \leq N \leq 1000$ and figure out its maximum. Here is a plot of $f(N)$:
The maximum occurs when $N=840$, and in this case $f(840) = \frac{195}{14} \approx 13.93$.
Asymptotic growth
If we investigate this function for very large $N$, we observe the following.
The lower bound on the plot is easy; it corresponds to the case when $N=p$ is a prime. In this case, we can apply the formula and immediately obtain $f(p) = 2-\frac{1}{p}$, which explains why it tends to $f(p)=2$ in the limit.
The upper bound (maximum value of $f(N)$) is not as clear. To investigate, I looked at several of the top-performing $N$ values to see if their prime factorizations were special in any way (the red points in the plot above). Here is what I found:
\begin{align}
N &= p_1^{a_1} \cdots p_m^{a_m} \\
12 &= 2^2 \cdot 3 \\
60 &= 2^2 \cdot 3 \cdot 5 \\
120 &= 2^3 \cdot 3 \cdot 5 \\
840 &= 2^3 \cdot 3 \cdot 5 \cdot 7 \\
2520 &= 2^3 \cdot 3^2 \cdot 5 \cdot 7 \\
5040 &= 2^4 \cdot 3^2 \cdot 5 \cdot 7 \\
27720 &= 2^3 \cdot 3^2 \cdot 5 \cdot 7 \cdot 11 \\
55440 &= 2^4 \cdot 3^2 \cdot 5 \cdot 7 \cdot 11 \\
360360 &= 2^3 \cdot 3^2 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \\
720720 &= 2^4 \cdot 3^2 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \\
\end{align}It appears that the top performing $N$ values are made up of small consecutive primes. I don’t have a complete explanation for this phenomenon, but here are some observations that may be relevant.
- A small prime raised to a large power is better than a large prime raised to a smaller power. Suppose $N = p^a$ is a power of a prime. Based on our formula, we have:
\[
f(p^a) = \frac{1}{p^a}\left( (a+1)p^a-ap^{a-1} \right) = 1+a\left(1-\frac{1}{p}\right)
\]So for a given $N$, we will get a larger value of $f(N)$ if it’s a small prime raised to a large power; so small primes are good! - A products of different primes is better than powers of the same prime. Suppose $p_1,\dots,p_m$ are distinct primes that are close together, so $p_i\approx p_j \approx p$. Note that:
\[
f(p_1 \cdots p_m) = \frac{(2p_1+1)\cdots (2p_m+1)}{p_1\cdots p_m} \approx \left(2+\frac{1}{p}\right)^m \sim 2^m
\]However, a power of the same prime yields something much smaller:
\[
f(p^m) = 1+m \left(1-\frac{1}{p}\right) \sim m
\]
So we should strive to use many distinct primes rather than repeating the same prime too many times.
This isn’t a complete explanation, but I think it illustrates the inherent trade-off present in maximizing $f(N)$.