Let $p_i$ always mean the $i$th prime number.
Given two numbers $a, b \in \Bbb{N}$ in the form $a = \{(p_i, e_i) : p_i^{e_i} \mid a, e_i \text{ maximal}\}$ ie. essentially their unique factorization, what is a natural way to compute whether $a \gt b$?
For instance a rule might be $p_{j}^2 \gt p_{j+1}$ always. So that given $a = 2^2$, $b = 3$, we immediately have $a \gt b$.
Is there a simple set of rules such that given the usual ordering on the primes and $1$: $1 \lt p_1 \lt p_2 \lt \dots$ we can always derive $a \gt b$ when it is true?
By no means can we include converting the number to a base representation and comparing the last digit.
It's best to work by example sometimes. Take $2 \cdot 7 \lt 3\cdot 5$. Well, $2 \lt 3 \lt 5 \lt 7$ so... ?
I'm stuck on this one, what is the simplest rule you can think of to overcome this example?
Here's some evidence that this may be hard.
In mathematical logic class we learn that the theory of $(\mathbb N,\times)$ is decidable. Basically, because the fundamental theorem of arithmetic states that the monoid of positive integers under multiplication $\times$ is a free commutative monoid on an infinite set of generators, the prime numbers.
But if we add in the relation $x< y$, you get the same definable sets as in all of first-order arithmetic $(\mathbb N,+,\times)$, which is not decidable. This is described by Alexis Bès.