0
$\begingroup$

Let $\{r_{1},\ldots,r_{K}\}$ be a collection of $K$ positive rational numbers.

How do I find the smallest positive integer $N$ such that $Nr_{k}$ is a positive integer for all $k$?

(Ideally, I am interested in a formula that is computationally cheap when $K$ is relatively large.)

$\endgroup$
1
$\begingroup$

You just need the least common multiple of the denominators once you express them in lowest terms. If you are given a numerator and denominator, you can check whether they have a common factor by the Euclidean algorithm. Divide that out to get all fractions in lowest terms. Then take the first two denominators, check for common factor, and form the least common multiple. Continue with each denominator in turn. This takes just two passes through the fractions, or one if you are guaranteed they are in lowest terms at the start.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I don't understand this part, which seems to be important: "Then take the first two denominators, check for common factor." Could you demonstrate with these numbers? 0.1519375, 0.02653125, 0.112875 $\endgroup$ – evencoil Jul 19 '18 at 21:26
  • $\begingroup$ I was assuming you had the rationals as integers for numerator and denominator. If you have them as floats, how do you know they are rationals? In your example, the first two are $\frac {2431}{16000}, \frac {849}{32000}$. The LCM of the denominators is $32000$. That will make those two into integers. If your next rational were $\frac 47$ you would need to multiply by $224000$ to get all three to be integers. $\endgroup$ – Ross Millikan Jul 19 '18 at 21:32
  • $\begingroup$ Got it now. Thanks $\endgroup$ – evencoil Jul 19 '18 at 21:38

Not the answer you're looking for? Browse other questions tagged or ask your own question.