A magical ordering of the positive integers

Question

Professor Erasmus told me this morning that he has constructed a magical ordering of the positive integers, which the professor modestly calls "The professor Erasmus ordering of the positive integers". This ordering $x_1,x_2,x_3,\ldots$ has the following striking properties:

• Every positive integer occurs exactly once in the ordering $x_1,x_2,x_3,\ldots$
• For all integers $m$ and $n$ (with $1\le m\le n$), the integer $m+n$ and the integer $x_m+x_n$ have the same number of divisors.
• There exists a positive integer $k$ so that $x_k\ne k$.

Question: Does such an Erasmus ordering indeed exist, or has the professor made a mistake?

Answer 1

Here is a sort of partial answer. It is an inductive proof but I'm missing a large chunck of what might be called the "base case".

Edit: This answer is (I hope) now complete. Thanks to f'' for filling in the gap.

---

Proposition: Given an ordering that meets the first two bullet points, it must be the third bullet point does not hold. That is, $x_k = k$ for all $k$.

Proof. Proof proceeds by induction. Suppose $x_i = i$ for $i < k$, and we want to show $x_k = k$.

Inductive case: We need a base case which we will get to later, but first suppose $k \geq 19$. There must be two square numbers in the range $k+1$ to $2k - 1$. For $i = 1, \ldots, k-1$, we know that $x_k + x_i = x_k + i$ has the same number of factors as $k+i$. Notice that square numbers are the only ones with an odd number of factors. Hence, $x_k$ must be the same distance to the next two square numbers as $k$. But since square numbers have a predictable increasing distance between them, the only possibility is if $x_k = k$.

Base case: We need to prove the statement for $k = 1$ through $k = 18$. Here we go:

• $k = 1$: We know that $x_1 + x_1 = 2x_1$ has the same number of factors as $1 + 1 = 2$, and hence $2x_1$ is prime. That is only possible if $x_1 = 1$.

• $k = 2$: Similarly, $2x_2$ must have exactly $3$ factors, but $4$ is the only even number with exactly three factors, so $x_2 = 2$.

• $k = 3$: We have $x_3 + x_2 = x_3 + 2$ is prime, and hence $x_3$ is odd. In fact, from this point on it will be easy to see that $x_k$ must have the same parity as $k$ based on distance to prime numbers. In this case,we have $x_3 + x_1 = x_3 + 1$ has three factors and is even, and hence $x_3 + 1 = 4$ and $x_3 = 3$.

• $k = 4$: We know $x_4$ is even (see note from $k = 3$ case). Hence $2 x_4$ is divisible by four and has the same number of factors as $8$. But $8$ is the only number divisible by $4$ with four factors, and hence $2 x_4 = 8$ and $x_4 = 4$.

• $k = 5, 6, 7$. Since $8$ is the only number divisible by four with $4$ factors, the pairs $6, 8$ and $8, 10$ are the only two pairs of even numbers two apart that both have four factors. We see $x_5$ is one away from such a pair and hence is $5$ or $7$, but it is easy to rule out $7$, so $x_5 = 5$. We have $x_6 = 6$ and $x_7 = 7$ similarly.

• $k = 8, 9, \ldots, 15$: $16$ is the only even number with $5$ factors. Since $2 x_8$ must have five factors, we see $x_8 = 8$. We see $x_9$ must be seven away from a even number with five factors, and hence $x_9 = 9$. Similar logic holds showing $x_{10} = 10$, $x_{11} = 11$, $\ldots$, $x_{15} = 15$.

• $k = 16, 17, 18$: Notice that $22$ has four divisors, $23$ is prime, and $24$ has $8$ divisors. Therefore $x_{16} + 6$ is even with four divisors, and hence not divisible by four. So $x_{16} + 8$ is divisible by four. We know $x_{16} + 6$ is even with four divisors, and hence not divisible by three. Since $x_{16} + 7$ is prime and not divisible by three, this forces $x_{16} + 8$ to be divisible by $3$. This means $x_{16} + 8$ is divisible by $12$. The only number divisible by $12$ with eight divisors is $24$, and hence $x_{16} + 8 = 24$ forcing $x_{16} = 16$. Similar logic proves $x_{17} = 17$ and $x_{18} = 18$.

$$\tag*{$\Box$}$$