Krdytkyu

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

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 japprox 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,bleq 53$, the easiest way to do this is to make an array of all possible ratios $frac l m$ for $l,mleq 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: $iapprox na$, so $napprox 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: $kapprox nc$, so $capprox frac k nrightarrow c=lceil frac k nrceil$. 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 $26cdot 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.

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.