CODEWITHSUNDEEP
javamath
Thomas Nappo
Thomas Nappo

Reputation: 251

What is the name for this, and how to calculate in Java?

I'm not good with mathematical terminology.

What is this called?

Say you have the number 48, you need to find two factors that make 48. In 48 would be 8,6 In 72 would be 9,8

I don't want say 12,4 for 48, or 12,6

Upvotes: 0

Views: 152

Answers (6)

Antimony
Antimony

Reputation: 39461

There is no particular name for the pair of factors with smallest distance. But it's easy to calculate if that's what you want. (At least as easy as factoring in general goes but for small numbers it's trivial.)

Here's one way to do it (which will be fastest when the two factors are close together.) It's based on Fermat's factoring algorithm.

static int sqrRoot(int n){
    //Find largest square <= n
    int sqr = 0;

    for (int i=15; i >= 0; --i){
        int newsqr = sqr + (1<<i);
        if (newsqr * newsqr <= n) {sqr = newsqr;}
    }

    return sqr;
}

static int[] closestFactors(int n){
    if (n <= 0) {throw new IllegalArgumentException();}

    int s = sqrRoot(n);
    if (s*s == n){
        int[] ans = {s,s};
        return ans;
    }

    int a = s * s - n;      
    while(s < n){
        if (a > 0){ //may not be true on first iteration
            int sa = sqrRoot(a);
            //whole number case
            if (sa*sa == a){    //We found a factorization
                int[] ans = {s-sa, s+sa};
                return ans;
            }
        }

        //half number case
        int sa2 = sqrRoot(a+s);
        if (sa2 * (sa2+1) == a+s){
            int[] ans = {s-sa2, s+sa2+1};
            return ans;
        }

        a += s + s + 1;
        s++;
    }

    int[] ans = {1, n};
    return ans;
}

Upvotes: 1

Firenze
Firenze

Reputation: 308

I don't think there's a particular name for numbers like that. As for finding them, the simplest way would probably be (given a number n):

int factor1, factor 2;
for (int i = (int)(Math.sqrt(n)); i > 0; i--) {
    if (i/n == (double)i/n) {
        factor1 = i;
        factor2 = i/n;
        break;
    }
}

Hope that helps!

Upvotes: 1

Stephen C
Stephen C

Reputation: 719346

I don't know of a name for this.

In Java you'd calculate this the same way as in any other language.

  1. Factorize the number.
  2. Figure out a partitioning of the set of factors into two subsets such that the difference between the products of the two sets is minimized. Brute-force should work as a first attempt ... unless there are a huge number of factors.

Note that in the worst case step 1. is NP, and step 2 (brute-force) is "only" O(F^3) where F is the number of factors.

An even more brute-force approach is to iterate over pairs of numbers in the appropriate range, testing to see if their product is the original number.

Coding and debugging is left as an exercise for the reader :-)

Upvotes: 1

Edmund
Edmund

Reputation: 10829

To factorise N in the usual case, a simple algorithm is to start at p = 2 and check if p divides N. If not, set p to the next value (e.g. next integer, or next prime number) and repeat.

In the ideal case for your problem, the factors will be close to sqrt(N). So you could start at p = floor(sqrt(N)) and decrement p until you find one which divides N.

Decrementing the test value each time will work. There may be mathematically smarter ways of doing it -- such as trying successive prime numbers, in the usual case. If a number can be factorised then a prime will do for a factor. But in your problem, you don't care about primes, so there might not be much use you can make of them here.

Upvotes: 1

Patrick87
Patrick87

Reputation: 28312

Clearly, you could find all factors and just choose the appropriate factors from the list.

As an alternative, you could start with low = high = floor(sqrt(n)). Then, if low * high < n, increment high; if low * high > n, decrement low; and if low * high = n, return (low, high) as the answer. This isn't terribly efficient, but you could probably make a couple of small optimizations.

Example:

n = 325
low = 18, high = 18, low * high = 324
low = 18, high = 19, low * high = 342
low = 17, high = 19, low * high = 323
low = 17, high = 20, low * high = 340
low = 16, high = 20, low * high = 320
low = 16, high = 21, low * high = 336
low = 15, high = 21, low * high = 315
low = 15, high = 22, low * high = 330
low = 14, high = 23, low * high = 322
low = 14, high = 24, low * high = 336
low = 13, high = 24, low * high = 312
low = 13, high = 25, low * high = 325
answer: 13, 25

This is rough, but an alternative to factoring. Note that any efficient solution to find two factors like this would be able to efficiently factor pseudo-primes used in cryptography, so you probably aren't going to get anything really fast.

Upvotes: 1

Thomas Nappo
Thomas Nappo

Reputation: 251

public static int[] revominuteFactors(long x) {
    int[] result = new int[2];
    for (int a = 0; a <= x; a++) {
        for (int b = 0; b <= x; b++) {
            if ((a * b) == x) {
                if (result[0] == 0 && result[1] == 0) {
                    result[0] = a;
                    result[1] = b;
                } else if (Math.abs(a - b) < Math.abs(result[0] - result[1])) {
                    result[0] = a;
                    result[1] = b;
                }
            }
        }
    }
    return result;
}

Asked a math professor, said it's name falls along the lines of revominute factors.

Upvotes: 2

Related Questions