0
$\begingroup$

Given a set of numbers, I need to find the lowest number that multiplying it with each of the numbers in the set results in a natural number, while being bigger or equal to $N$.

For example, for the numbers $2.2$, $3$ and $4.2$, the result could be $5$, $10$, $15$, etc as they can multiply $2.2$ and $4.2$ and result in natural numbers. Then, I need the lowest one that's higher than a given number.

I'm trying to implement it as a software algorithm in an efficient way. How would I go about doing that?

1 Answers 1

2

First find the least common multiple of the denominators. You have to multiply by that to clear the fractions, so do so. Then if $a$ is the smallest number after multiplying by the LCM, divide $N$ by $a$ and round up to the next whole number. Call that $b$. The multiplier for the original set is $b*LCM$

  • 0
    Would that give me the smallest number possible? How would I go from there to finding the smallest one that's larger than N?2012-10-21
  • 0
    @shesek: I misread the problem, thinking you just wanted the product larger than the largest in your original set. Fixed.2012-10-21
  • 0
    When referring to "a is the smallest number", you mean after multiplying all the numbers by the lcm, right?2012-10-21
  • 1
    @shesek: It would be clearer to make it so. I was thinking that $a$ was the original smallest number, which is why I said to divide by $a * lcm$. Now it will just be $a$. I will update2012-10-21
  • 0
    Lets say the numbers are $3$ and $7$, and the multiplier should be larger than $50$ ($N$). The LCM would be $21$, $a$ would be $63$ ($3*LCM$), $b$ would be $1$ ($ceil(N/a)$), and the result would be $21$ ($b*LCM$). The number is lower than $N$. With $5,6,7$ and $N=5$, I'm getting $210$. Because all the numbers are natural, any natural number that's >= $N$ could satisfy it (its gets tricky when dealing with decimals), so the result should be $N$ for both of them. It seems I either misunderstood you, or you misunderstood my question. Thanks for your help and time :)2012-10-21
  • 1
    @shesek: the LCM is taken over denominators. So if you have 3 and 7 and $N=50$, the LCM of the denominators is 1, then $b=17$2012-10-21
  • 0
    Oh, sorry, I misread. Let me try again... thanks.2012-10-21
  • 0
    but then, with b=17 and LCM=1, $b*LCM$ is $17$, lower than $N$.2012-10-21
  • 0
    @shesek: this is the multiplier. So if $b=17$ that is what you multiply by. $3*17=51\gt 50$2012-10-22