Smallest integer satisfying inequality

Question

I am looking for the smallest numbers $m_a'$ and $m_b'$ so that they have n decimals and following expressions still hold: \begin{equation} \begin{cases} \frac{m_a'}{m_b'}=\frac{C_a}{C_b} \\ m_a'\geq m_a\\ m_b' \geq m_b \end{cases} \end{equation}

I know this is possible with a for loop, but since computation time is very important I wonder if there is a mathematical solution for this problem (using for example $ceil$ and $floor$ functions)? I have tried to solve this by rewriting $m_a'$ and $m_b'$ as follow: \begin{equation} \begin{cases} m_a'=l_a*n_d\\ m_b'=l_b*n_d\\ \end{cases} \end{equation} Where $l_a$ and $l_b$ are two integers and $n_d$ the number of decimals which are required (ex. $n_d=0.01$ for 2 decimals). Then I use this together with the two inequalities: \begin{equation} \begin{cases} \frac{m_a'}{m_b'}=\frac{C_a}{C_b}=\frac{m_a}{m_b}\frac{k}{k} \\ k*l_a \geq \frac{m_a}{n_d} \\ k*l_b \geq \frac{m_b}{n_d} \\ \end{cases} \end{equation}

At this stage I should search for the smallest $l_a$ and $l_b$ satisfying conditions above, but I do not know how to proceed at this point.

Answer 1

The first equality means that $\frac{C_a}{C_b}$ is rational thus we can write it as $\frac{p}{q}$ with p,q coprime integers. you can replace $m_{a'}$ by $m_{b'}$ on the first equality: $m_{a'}= \frac{p}{q}m_{b'}$ and then we replace it in the inequality: $\frac{p}{q}m_{b'} \geq m_a$ and thus $m_{b'} \geq max(\frac{q}{p}m_a, m_b)$ and since $m_{b'}$ has to be an integer we need to ceiling that number and since $m_{a'}$ has to be an integer $m_{b'}$ has to be divisble by q: $m_{b'} = q \cdot \text{ceil}(\text{ceil}(\text{max}(\frac{q}{p}m_a, m_b))/q)$

from math import ceil
from fractions import Fraction

def smallest_inst(CaCb, ma, mb):
    frac = Fraction(CaCb).limit_denominator(1000)
    p = frac.numerator
    q = frac.denominator
    mb_res = q*ceil(ceil(max(q/p *ma, mb))/q)
    ma_res = int(mb_res*p/q)
    assert abs(ma_res/mb_res - CaCb) < 1e-10
    assert ma_res >= ma
    assert mb_res >= mb
    return ma_res, mb_res

ma=4000
mb=1200
CaCb = 3.1415929203539825 # Ca/Cb
print(smallest_inst(CaCb, ma, mb))
(4260, 1356)

Finding p and q is the bottleneck. Which is a greatest common divisor kind of problem.