Find common factors of three rounded integers

Question

I'm trying to find the common factor(s) of three integers which have each been rounded up to the next multiple of 8:

• i = round(n * a)
• j = round(n * b)
• k = round(n * c)

I'm given i, j, and k and I'm trying to find n. The rounding for all three is always to the next multiple of 8.

I could probably handle the simultaneous equation or finding the factor(s) on my own, but I'm a programmer and not a mathematician and don't know how to handle the complication added with the rounding mathematically. (Stackoverflow said I should ask the question here though.)

---

Real-world example:

i = 33475329 * 8, a = 42 j = 21519854 * 8, b = 27 k = 18331728 * 8, c = 23

n = 6376253

Answer 1

First, I think we basically have to assume $a,b,c$ are coprime in order to find $n$. Otherwise, you run into the problem Ross Millikan pointed out where $n$ is ambiguous and depends on knowing the common factor between $a,b,c$. Thus, the rest of this solution is going to assume $a,b,c$ are coprime. For example, if the choice is between $(a,b,c)=(46, 18, 54)$ and $(a,b,c)=(23, 9, 27)$, we will choose the latter.

Honestly, I still think the brute force solution is the easiest way to do this. However, I have found a slightly faster solution, although it requires more precomputation. First, I will assume $n$ is very big, so the change from $na$ to $i$, which is just $na$ rounded up to the nearest multiple of $8$, is a very small percent change. For instance, in your example, $i$ is $267802632$ while $na$ is $267802626$, which is a percent change in about $.000002\%$, which is quite small indeed.

Therefore, because of these small percent changes, the ratios between $i,j,k$ are very similar to the ratios between $na,nb,nc$. For instance, in your example $\frac i j$ is $1.5555555813715094$ while $\frac{na}{nb}$ is $1.5555555555555556$, which are very close to each other. However, $\frac{na}{nb}$ simplifies to $\frac a b$, so we get: $$\frac i j\approx \frac a b$$ Now, we know the ratio between $a$ and $b$. However, how do we solve for $a$ and $b$ based off this ratio? Since $a,b\leq 53$, the easiest way to do this is to make an array of all possible ratios $\frac l m$ for $l,m\leq 53$ and do a binary search for $\frac i j$ to find what $a$ and $b$ should be.

Now, from here, finding $n$ is easy: $i\approx na$, so $n\approx \frac i a$. Since we know $n$ is an integer, we can just say $n=\lceil \frac i a \rceil$ and call it a day. Once we know $n$, finding $c$ is also easy: $k\approx nc$, so $c\approx \frac k n\rightarrow c=\lceil \frac k n\rceil$. Thus, we have found $n$, $a$, $b$, and $c$, so we are done.

There is one ambiguity to this, however: If the ratio between $a$ and $b$ has small numerator and denominator, like $\frac 3 4$, how do we know if the solution is $(a,b)=(3,4)$ or $(a,b)=(6,8)$? Now, because we want $a,b,c$ to be coprime, but this does not necessarily mean $a,b$ are coprime. For instance, in your example, $a,b,c$ are coprime, but $a,b$ has common factor of $3$. Therefore, when we find $n$ and $c$, we need to test that $i,j,k$ are indeed $na,nb,nc$ rounded up to the nearest integer and if they are not, we need to multiply $a,b$ by some common factor in order to test if that new common factor leads to a new value of $n$ and $c$ which works. Again, using your example, this means we will first test $(a,b)=(14,9)$, then $(a,b)=(28,18)$, then $(a,b)=(42,27)$ before finally getting the correct solution.

Using all of this analysis, we can construct the following solution:

import math
import bisect

# This array holds all ratios l/m where 1 <= l,m <= 53 and l,m are coprime
ratios = []
for l in range(1, 54):
    for m in range(1, 54):
        if math.gcd(l, m) == 1:
            ratios.append((l/m, l, m))
# Sort the ratios into increasing order:
ratios = sorted(ratios)

def compute_nabc(i, j, k):
    '''
    This function computes the values of n, a, b, and c
    based off the values of i, j, and k.
    '''
    # Find the index where i/j would be put in the ratios array
    ij_index = bisect.bisect(ratios, (i/j, i, j))
    # error_on_left is the absolute difference between i/j
    # and the greatest ratio in ratios less than i/j
    error_on_left = math.inf
    if ij_index-1 > 0:
        error_on_left = abs(i/j-ratios[ij_index-1][0])
    # error_on_right is the absolute difference between i/j
    # and the least ratio in ratios greater than i/j
    error_on_right = math.inf
    if ij_index < len(ratios):
        error_on_right = abs(i/j-ratios[ij_index][0])
    # If the error_on_left is less, take a and b from the lesser ratio:
    if error_on_left < error_on_right:
        smallest_a = ratios[ij_index-1][1]
        smallest_b = ratios[ij_index-1][2]
    # Otherwise, take a and b from the greater ratio:
    else:
        smallest_a = ratios[ij_index][1]
        smallest_b = ratios[ij_index][2]
    # Notice how the above variables are named smallest_a and smallest_b.
    # This is because they are the values of a, b which are coprime.
    # However, it is possible that a, b have some common factor d,
    # so let's loop through d:
    # (Given a,b <= 53, the greatest possible common factor is 53/2=26.)
    for d in range(1, 27):
        # Compute a and b by multiplying d by the smallest_a and smallest_b:
        a = d*smallest_a
        b = d*smallest_b
        # i is about na, so n is about i/a:
        n = round(i/a)
        # k is about nc, so c is about k/n:
        c = round(k/n)

        # Now, at the end here, we are simply verifying that
        # i, j, k are indeed na, nb, nc rounded up to the nearest integer.
        # If not, then we continue to the next value of d.
        if i != 8*math.ceil(n*a/8): pass
        elif j != 8*math.ceil(n*b/8): pass
        elif k != 8*math.ceil(n*c/8): pass
        # Otherwise, if everything's good, we exit
        else: break

        # If d is 26 and we never found an answer, print error message
        if d == 26:
            print("ERROR: Valid answer not found")

    # Finally, return n, a, b, and c in a 4-tuple
    return (n, a, b, c)

# Outputs (6376253, 42, 27, 23)
print(compute_nabc(33475329*8, 21519854*8, 18331728*8))
# Outputs (201720, 23, 9, 27)
print(compute_nabc(579945*8, 226935*8, 680805*8))
# Outputs (38587389, 33, 23, 45)
print(compute_nabc(159172980*8, 110938744*8, 217054064*8))
# Outputs (6371253, 52, 26, 33)
print(compute_nabc(41445645*8, 20722823*8, 26302044*8))

Now, the pre-computation is about $53^2=2809$ operations, which is slower than brute force of $512$ operations. However, the actual compute_nabc function only takes $\lceil \log_2(2809)\rceil=12$ comparisons for binary search and about $26\cdot 4=$ operations, at most, for testing the different possible values of $n,c$, so the actual compute_nabc function is about $5$ times less operations than brute force. Thus, although it might not make an actual difference since brute force is still pretty fast, if you are OK with doing a lot of pre-computation and have to execute compute_nabc dozens or hundreds of times, it might be easier to use this approach than brute force.

Answer 2

You can't with the data you are given. Let $a,b,c$ be close, say $b=a+1, c=a+2$ and $n$ be $4$. You can't tell from the case where $n$ is $2$ and the others are doubled.