Fix two primes p and q. Given input a number of the form $p^aq^b$, find the immediate next number of the same form

As stated in the title:
Fix two primes p and q. Given input a number of the form $p^aq^b$, find the immediate next number of the same form.

For example: when $p = 2$ and $q = 3$
Next of $2^23=12$ is $2^3=16$ and after that is $23^2=18$

Question [edited]:

Can this be done in poly-time of the representation of $a$ and $b$?

I believe so and I do have a sketch for this, but I want to see what a "proper" answer to this question is.

Let $c = \log p$ and $d = \log q$. Then $\log (p^a q^b) = ca + db$. Define the set $S_{c,d} = \{ci+dj : i,j \in \mathbb{N}\}$. Your problem is equivalent to the following:


Problem 1. Given $a,b \in \mathbb{N}$ and $c,d \in \mathbb{R}$, find $a',b' \in \mathbb{N}$ so that $ca' + db'$ is the next attainable real number in $S_{c,d}$ after $ca + db$.

This is in turn equivalent to the following problem:


Problem 2. Given $\alpha \in \mathbb{R}$ and $X,Y \in \mathbb{Z}$, find $x,y \in \mathbb{N}$ that minimizes $x+\alpha y$, subject to the requirements that $x \ge X$, $y \ge Y$, and $(x,y) \ne (0,0)$.

(The equivalence can be seen by letting $\alpha = d/c$, $X=-a$, $Y=-b$, and $x=a'-a$, $y=b'-b$.)

Problem 2 now amounts to finding the best rational approximation $x/y$ of $-\alpha$, subject to constraints on the size of $x,y$. There are many techniques for that, including continued fractions. You can also express this as the problem of finding a closest lattice point to $(0,0)$ in a certain two-dimensional lattice. There are many algorithms for closest lattice point search in lattices, also known as the closest vector problem; in two dimensions, I believe they run in polynomial time, if I remember correctly. See, e.g., https://mathoverflow.net/q/61897.

StackExchange Computer Science Q#32043, answer score: 4