List naturals in ascending product order Define an ascending product ordering as a sequence $(x_1,y_1), (x_2,y_2), \ldots$ with the following properties:


*

*Each pair of naturals is represented: For any integers $a\ge b>0$, we know that $(a,b)=(x_n,y_n)$ for some $n$.

*The order is sorted in ascending product order: $x_n y_n \le x_my_m$ for all $n<m$.
Are there any ascending product orderings where $(x_i,y_i)$ can be computed very efficiently for any $i>0$?
I'm wondering how well we can describe the "zig-zag" pattern that such an order must follow.

The above path goes through the following points:
(1, 1), (2, 1), (3, 1), (2, 2), (4, 1), (5, 1), (3, 2), (6, 1), (7, 1), (4, 2), (8, 1), (3, 3), (9, 1), (5, 2), (10, 1), (11, 1), (4, 3), (6, 2), (12, 1), (13, 1), (7, 2), (14, 1), (5, 3), (15, 1), (4, 4), (8, 2), (16, 1), (17, 1), (6, 3), (9, 2), (18, 1), (19, 1), (5, 4), (10, 2), (20, 1), (7, 3), (21, 1), (11, 2), (22, 1), (23, 1), (6, 4), (8, 3), (12, 2), (24, 1), (5, 5), (25, 1), (13, 2), (26, 1), (9, 3), (27, 1), (7, 4), (14, 2), (28, 1), (29, 1)
 A: While there are many possible sequences $(x_1,y_1), (x_2,y_2),\ldots$ there is only one allowed product sequence $x_1y_1,x_2y_2,\ldots$. Thus the first step is more or less necessarily to determine $p_i=x_iy_i$ for given $i$ (or else we could obtain $p_i$ in the end at the cost of just one multiplication). If one additionally finds the unique $j<i$ with $p_j<p_{j+1}=p_i$, we can simply let $y_i$ be the $(i-j)$ smallest divisor of $p_i$ and $x_i=\frac{p_i}{y_i}$. At any rate, the algorithm cannot be essentially faster than a complete factorization of $p_i$. Also, any (other) algorithm to efficiently compute $(x_i,y_i)$ can be turned into an algorithm to compute the number of divisors of all integers $\le p_i$ (by determining the $j$ above).
While these ideas indeed lead to an algorithm to compute $(x_i,y_i)$, it appears to be exponential in nature because it is essentially equivalent to complete factorizatuon of arbitrary integers ...
A: If the point $(x,y)$ is $(p,1)$ where $p$ is a prime, then its position in the list is 
$$1+\sum_{k=1}^{p-1} \operatorname{ceiling}\frac{d(k)}{2} ,$$
where $d(k)$ is the number of divisors of $k$. Ordered pairs $(x,y)$ whose product $xy$ is composite might have various positions in the list depending on how you choose to arrange pairs with the same product.
A: I do not want to give a complete answer, just a hint (but I am afraid it does not fit as a comment).
I suggest you consider the partial order defined by the following equivalence:


*

*$(x,y) \leq (x',y')$, iff

*either $x \cdot y < x' \cdot y'$ or ($x \cdot y = x' \cdot y'$ and $x \geq x'$).


What I do not want to write down is how to transform this definition into a sequence $(x_1,y_1),(x_2,y_2), \ldots$. Let me leave this as an exercise, but is very easily computed.
