Method of finding "closest" common multiple?

42 Views Asked by At

I am trying to program a script to do this, but I can't find any existing methods, so I hope you have any ideas. The problem is similar to LCM, but the numbers are inaccurate, so I have to find the closest solution.

Example: I have the numbers 1296, 306, 8928, 2466, 1881. They should be multiples of the number 180, but since the numbers are inaccurate, I need to find a number that is close to 180, that gives the least amount of error as multiple for the set of numbers.

Any ideas on how I can solve this?

1

There are 1 best solutions below

0
On

I am confused by what you intend by "I need to find a number that is close to 180, that gives the least amount of error as multiple for the set of numbers."

I am guessing that you want each number $n$ converted to $m$, where $m$ is the closest multiple of $180$ to $n$. Assuming so, after the conversion, you could then (for example) compute the lcm of $\{m_1, m_2, m_3, m_4, m_5\}$ using standard methods.

If my guess and subsequent analysis is accurate, then your query reduces to how to convert a positive integer $n$ into $m$.

Apply the Euclidean Algorithm so that
$n = (90\times P) + r$,
where $P \,\in \{0,1,2,\cdots\}$ and $r \in \{0,1,2,\cdots, 89\}.$

Then, if $P$ is even, then the closest multiple $$m = 180 \times \left(\frac{P}{2}\right).$$

Alternatively, if $P$ is odd, then the closest multiple $$m = 180 \times \left(\frac{P+1}{2}\right).$$

The only wrinkle is that if $P$ is odd and $r = 0$, then $n$ is equidistant between two multiples of 180 and my algorithm is (then) automatically "rounding up".