4
$\begingroup$

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^2*3=12$ is $2^3=16$ and after that is $2*3^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.

$\endgroup$
  • $\begingroup$ I don't see how it could be done in constant time. As $a$ and $b$ get large, even producing the output would not be constant in time or memory. More speculatively, I don't think there is a simple relationship that would allow the determination of the answer quickly, my first-approximation guess is that this would take pseudopolynomial time (polynomial in the magnitude of $a$ and $b$, but maybe exponential in the size of their representation). $\endgroup$ – Luke Mathieson Oct 18 '14 at 11:22
  • $\begingroup$ @LukeMathieson Fair suggestion. I am hoping to get it in time that is not exponential to the representation of $a$ and $b$ $\endgroup$ – InformedA Oct 18 '14 at 16:30
  • $\begingroup$ If you have a sketch you should share it with us. Otherwise it's pointless to think about the question. This is not a puzzle site. $\endgroup$ – Yuval Filmus Oct 20 '14 at 4:06
  • $\begingroup$ @YuvalFilmus I have a sketch, but I am not sure if that will be correct, so I refrain from writing it here. I have learnt the hard way that the real world is not like a school exam. You don't say anything to get partial credit. In the real world, wrong answers are not something with which you can be easy. $\endgroup$ – InformedA Oct 20 '14 at 4:17
  • $\begingroup$ Have you empirically tested your algorithm? Do you have a candidate proof? $\endgroup$ – Yuval Filmus Oct 20 '14 at 11:46
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hello, thank you very much for this response. I just want to note that I was hoping to put more focus on the fact that the 2 primes $p$ and $q$ are fixed. This means that any cost associated with only $p$, $q$ even exponential is considered a constant. $\endgroup$ – InformedA Oct 20 '14 at 1:41

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.