Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Say we have a set $S$ of $n$ irrational numbers $\left\{a_1, ..., a_n\right\}$.
Are there any known algorithms that can determine a scaling factor $s \in \mathcal{R}$ such that $s * a_i \in \mathcal{N} \;\forall a_i \in S$, assuming that such factor exists? If multiple exist, how about the smallest one?
Moreover, I wonder, under what input conditions could one assume that an algorithm for this problem can't (or can) return a valid scaling factor?
I'm assuming that $0 \not \in \mathbb{N}$, otherwise $s=0$ is a trivial solution.
If you input numbers contain at least one positive and one negative number there is no solution. If your input numbers are all negative, either there is a solution but no smallest solution, or there is no solution at all. You can decide which of the two is the case by solving the same problem on with the numbers multiplied by $-1$.
Assume then that all input numbers are positive.
If $s a_1 = c$ and $s a_2 = c'$ for $c,c' \in \mathbb{N}$, then $c' = s a_2 = c \frac{a_2}{a_1}$, i.e., $\frac{a_2}{a_1}= \frac{c'}{c}$. This shows that you can only find a solution if all your irrational numbers can be obtained by multiplying $a_1$ by some rational factor.
In this case you can consider the set of numbers $\{1, \frac{a_2}{a_1}, \frac{a_3}{a_1}, \dots, \frac{a_n}{a_1}\}$ instead. Since they are all rationals you can write them as $\{1, \frac{b_2}{c_2}, \frac{b_3}{c_3}, \dots, \frac{b_n}{c_n}\}$, where $b_i,c_i \in \mathbb{N}$ and $gcd(b_i,c_i)=1$. You can then find the minimum common multiple of the denominators and multiply it by $a_1^{-1}$.
