12
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ For the 3rd property, is this true of exactly one k or at least one ? $\endgroup$ – ABcDexter Mar 29 '16 at 14:15
  • 2
    $\begingroup$ @ABcDexter: This is true for at least one $k$. This is exactly as in everyday language. If you say "There exists a human being with black hair", you also mean "at least". $\endgroup$ – Gamow Mar 29 '16 at 14:32
  • 2
    $\begingroup$ Since it is Prof Erasmus and not prof Halfbrain I would say there is such an order, but not sure about it :) $\endgroup$ – Marius Mar 29 '16 at 14:35
  • 1
    $\begingroup$ @Ivo Beckers: Not necessarily. I have edited the statement, so that this becomes clear. $\endgroup$ – Gamow Mar 29 '16 at 14:38
  • 2
    $\begingroup$ My guess is it is false. Such an ordering would mean that for all $a$, $1+a$ has the same number of factors as $x_1 +x_a$. That would mean that $x_1$ shares the same properties as $1$ when adding to numbers. To me, this means that $x_1=1$, although I can't see an easy way to prove it. Likewise, one should be able to see that $x_k=k$ for all $k$ simply by proving that $k$ and $x_k$ modify numbers the same way. $\endgroup$ – Trenin Mar 29 '16 at 16:59
7
$\begingroup$

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$}$$

$\endgroup$
  • $\begingroup$ Not sure if it helps but I think you can conclude that if $k$ is a prime that $x_k$ must also be a prime. because then $x_k + x_k$ must have 4 divisors and that is only the case with primes where two times a number has 4 divisors I think $\endgroup$ – Ivo Beckers Mar 29 '16 at 20:15
  • $\begingroup$ @IvoBeckers: Didn't happen to be helpful but very clever. f'': Thanks, looks great! I took the liberty of adding all your comments to the post so the proof would be complete. $\endgroup$ – Tyler Seacrest Mar 30 '16 at 4:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.