# Ordering pairs of integers $(n, m)$ by the value of ${k_1}^n{k_2}^m$

Ok, so I have two positive integers $k_1$ and $k_2$ raised to positive integer powers $n$ and $m$ respectively. My question is how could I create a list of $(n, m)$ values such that the corresponding values of ${k_1}^n{k_2}^m$ are in ascending order. Is there a pattern which could be used to create a list of $n$ and then $m$ values, for example? Or perhaps a simple algorithm that could do the trick - I've had a go and didn't seem to get anywhere (without of course using brute force).

If there is a nice solution, something else I would like to know is how this might be extended to the product of any number of integers $k$ and power values.

EDIT: I've just had a go with $k$ values 2 and 3, and have found that for $n$ (the power of 2) the $j^2+j$th $n$ in the list where $j$ is a positive integer seems to be 0.

Thanks :)

• Are you looking for a general rule or just an efficient algorithm that you can implement on a computer? Commented Mar 1, 2017 at 16:53
• @RazimanTV Either would be good but I think a general rule would be a preferrable solution. Commented Mar 1, 2017 at 16:57

Take $a, b, c, d \in \mathbb{Z}$ and $x, y \in \mathbb{R}_{> 0}$. We aim to decide whether $x^a y^b > x^c y^d$. If $x = 1$ the problem is obvious. Otherwise $log(x) \neq 0$. If $d = b$ then likewise the problem is obvious. Otherwise $d - b \neq 0$. Hence assume that $log(x) \neq 0$ and that $d - b \neq 0$, so that we can make the following calculation: \begin{align*} & x^a y^b > x^c y^d \\ \iff & log(x^a y^b) > log(x^c y^d) \\ \iff & a* log(x) + b *log(y) > c *log(x) + d *log(y) \\ \iff & (a - c) log(x) > (d - b) log(y) \\ \iff & \frac{a - c}{d-b} > \frac{log(y)}{log(x)} \end{align*} Hence one possible algorithm could calculate (once and for all) the value of $\frac{log(y)}{log(x)}$ to a reasonable accuracy. Then, given tuples of integers $(a, b)$ and $(c ,d)$, calculate $\frac{a - c}{d-b}$ and test for whether the value is greater than $\frac{log(y)}{log(x)}$. Of course, this pairwise algorithm could then be used to order a list using a sorting algorithm.

For the general case, take positive real numbers $x_1, ..., x_n$. One possible algorithm would simply calculate $(y_1, ..., y_n) = (log(x_1), ..., log(x_n))$ once and for all, to a reasonable accuracy. Then, given integers $a_1, ..., a_n$, $b_1, ..., b_n$, test for whether $(a_1 - b_1, ..., a_n - b_n) \cdot (y_1, ..., y_n) > 0$.

Here is an algorithm to generate the first $N$ numbers of the for $k_1^n k_2^m$.

Clearly the first number in the list is zero. After this, note that every following number is $k_1$ or $k_2$ times a previous number. Also, since we generate the list in increasing order, we can multiply each element by $k_1$ and $k_2$ in the increasing order as well. In this fashion, at each step, there are only two candidates for the next element in the sequence: we only need to compare these two to see which of them is larger and move to the next candidate element.

So the algorithm goes as such:

generatelist(k1, k2, N):
list = {1}
L = 1 // Current size of list
p1 = 1, p2 = 1 // Elements of the list to be multiplied by k1 and k2

while L < N:
c1 = list[p1] * k1, c2 = list[p2] * k2 // Candidates
if c1 < c2:
list.push_back(c1)
p1 = p1 + 1
else if c2 < c1:
list.push_back(c2)
p2 = p2 + 1
else:
list.push_back(c1)
p1 = p1 + 1
p2 = p2 + 1
L = L + 1

return list


If you want to generate all $N$ elements in the list, this algorithm has $O(N)$ complexity and you can hardly do better asymptotically. If you just want to find the $N$th element, there might be better methods.

If you are looking for a general rule, I doubt that one exists. This problem is equivalent to minimising $n \log k_1 + m \log k_2$, and there is no straightforward rule for that unless the logarithms are rational multiples of each other.

• Thanks, I'll try it out and see if I can find a general rule from it :) Commented Mar 1, 2017 at 17:15