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.

Improve this question
$\endgroup$
6
  • $\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$ Commented Oct 18, 2014 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$ Commented Oct 18, 2014 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$ Commented Oct 20, 2014 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$ Commented Oct 20, 2014 at 4:17
  • $\begingroup$ Have you empirically tested your algorithm? Do you have a candidate proof? $\endgroup$ Commented Oct 20, 2014 at 11:46

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
1
  • $\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$ Commented Oct 20, 2014 at 1:41

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.