Input an integer, find the two closest integers which, when multiplied, equal the input

StackOverflow https://stackoverflow.com/questions/16266931

Question

Ok my problem is of mathematical nature. I have an array of bytes whose length is X, i need to find the two closest numbers which multiplied together equal X. I need to do this because i am bulding a bitmap from an array of bytes and i need to make the bitmap look like a square as much as possible. I am coding this in C# but don' t worry about syntax, any algorithm or pseudo-code will do. Thanks in advance for your help

Was it helpful?

Solution 3

There's probably a better algorithm for this, but off the top of my head:

1) Take the square root of the number X; we'll call it N.
2) Set N equal to the ceiling of N (round up to the nearest integer).
3) Test for (X % N). If N divides evenly into X, we found our first number.
  if 0, divide X by N to get M. M and N are our numbers
  if not 0, increment N by 1 and start step 3 over.

OTHER TIPS

I am not allowed to comment yet so here is a quick python>=3.8 implementation based on @Anthony DeSimone's answer modified to using floor() as suggested by @Egor Skriptunoff:

import math
def sqrt_int(X: int):
    N = math.floor(math.sqrt(X))
    while bool(X % N):
        N -= 1
    M = X // N
    return M, N

Note that if X is at all large, then starting from sqrt(X) and working downwards one step at a time will be a miserable task. This may take a huge amount of time.

If you can find the factors of the number however, then simply compute all divisors of X that are less than sqrt(X).

Consider the number X = 123456789012345678901234567890. The smallest integer less than sqrt(X) is 351364182882014, so simply decrementing that value to test for a divisor may be problematic.

Factoring X, we get this list of prime factors:

{2, 3, 3, 3, 5, 7, 13, 31, 37, 211, 241, 2161, 3607, 3803, 2906161}

It is a fairly quick operation to compute the divisors less then sqrt(N) given the prime factors, which yields a divisor 349788919693221, so we have

349788919693221 * 352946540218090 = 123456789012345678901234567890

These are the closest pair of divisors of the number N. But, how many times would we have needed to decrement, starting at sqrt(N)? That difference is: 1575263188793, so over 1.5e12 steps.

A simple scheme to determine the indicated factors (in MATLAB)

Dmax = 351364182882014;
F = [2, 3, 3, 3, 5, 7, 13, 31, 37, 211, 241, 2161, 3607, 3803, 2906161];
D = 1;
for i = 1:numel(F)
  D = kron(D,[1,F(i)]);
  D = unique(D);
  D(D > Dmax) = [];
end

D(end)
ans =
     349788919693221

The other factor is obtained simply enough. If the numbers are too large to exceed the dynamic range of a flint as a double, then you will need to use some variation of higher precision arithmetic.

I have rewritten the MATLAB answer proposed above by user85109 in a detailed function with sufficient comments and some simpler terms. Certainly quite efficient, works for large numbers and hopefully easy to write in any language which provides a library function for getting prime factorization of an integer. 

        function [a, b] =  findIntegerFactorsCloseToSquarRoot(n)
        % a cannot be greater than the square root of n
        % b cannot be smaller than the square root of n
        % we get the maximum allowed value of a
        amax = floor(sqrt(n));
        if 0 == rem(n, amax)
            % special case where n is a square number
            a = amax;
            b = n / a;
            return;
        end
        % Get its prime factors of n
        primeFactors  = factor(n);
        % Start with a factor 1 in the list of candidates for a
        candidates = [1];
        for i=1:numel(primeFactors)
            % get the next prime factr
            f = primeFactors(i);
            % Add new candidates which are obtained by multiplying
            % existing candidates with the new prime factor f
            % Set union ensures that duplicate candidates are removed
            candidates  = union(candidates, f .* candidates);
            % throw out candidates which are larger than amax
            candidates(candidates > amax) = [];
        end
        % Take the largest factor in the list d
        a = candidates(end);
        b = n / a;
    end

A perfect square would have a side of SQRT(X) so start from there and work downward. 

int X = ...
for(int i=sqrt(x);i>0;i--) {
  // integer division discarding remainder:
  int j = X/i;
  if( j*i == X ) {
    // closest pair is (i,j)
    return (i,j);
  }
}
return NULL;

Note this will only work if X is actually divisible by two integers (ie a prime X is going to end up with (1,X)). Depending on what you're doing you might better off picking slightly larger dimensions and just making it square ... ie have the sides be CEILING(SQRT(X)).

One alternative is to set up this optimization problem

Minimize the difference of the factors X and Y the difference of the product X × Y and P. You have thus an objective function that is weighted some of two objective:

       min c × |X × Y - P|  +  d × |X – Y|
subject to X, Y ∈ ℤ
           X, Y ≥ 0

where c, d are non-negative numbers that define which objective you value how much.

Like the sqrt solution a lot however : )

Thanks for your answers. I have made a function that finds the closest 3 integers building on the sqrt approach:

function [a, b, c] =  findIntegerFactorsCloseToCubeRoot(n)
% a cannot be greater than the cube root of n
% b cannot be smaller than the cube root of n
% we get the maximum allowed value of a
amax = floor(nthroot(n,3))
if amax^3 == n
    % special case where n is a cube number
    a = amax;
    b = a;
    c = a;
    return;
end
% Get its prime factors of n
primeFactors  = factor(n);
% Start with a factor 1 in the list of candidates for a
candidates = [1];
for i=1:numel(primeFactors)
    % get the next prime factor
    f = primeFactors(i);
    % Add new candidates which are obtained by multiplying
    % existing candidates with the new prime factor f
    % Set union ensures that duplicate candidates are removed
    candidates  = union(candidates, f .* candidates);
    % throw out candidates which are larger than amax
    candidates(candidates > amax) = [];
end
% Take the largest factor in the list d
a = candidates(end);
% call similar function for remaining 2 factors
[b, c] = findIntegerFactorsCloseToSqRoot(n/a);
end

This answer (in python3) borrows from Shailesh Kumar, which itself borrows from user85109.

Both prior answers failed to address low self-multiples of prime factors, which meant that values (under 100) such as [18, 22, 26, 34, 38, 46, 58, 62, 66, 68, 70, 74, 76, 78, 82, 84, 86, 87, 92, 93, 94, 96, 98] fail.

The following fixes that, and is fast enough for large numbers. I also used the set structure while building candidates, as sets provide uniqueness 'for free', at the (lower) cost of a final conversion and sort.

Because the candidates include factors which do not divide n as an integer, we have to finally ensure that the condition is met.

import math
from sympy.ntheory import primefactors


def int_root(n: int) -> tuple:
    root_n = math.sqrt(n)
    if 0 == n % root_n:
        a = int(root_n)
        return a, n // a
    pfs = primefactors(n)
    candidates = {1}
    for pf in pfs:
        for fi in range(math.ceil(math.log(root_n, pf))):
            candidates = candidates | {pf * c for c in candidates if pf * c < root_n}
    candidates = {c for c in candidates if n / c == n // c}
    a = max(candidates)
    return a, n / a


if __name__ == '__main__':
    for i in [18, 22, 26, 34, 38, 46, 58, 62, 66, 68, 70, 74, 76, 78, 82, 84, 86, 87, 92, 93, 94, 96, 98]:
        r = int_root(i)
        print(i, r)
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top