Integer distance

Question

As a single operation between two positive integers we understand multiplying one of the numbers by some prime number or dividing it by such (provided it can be divided by this prime number without the remainder). The distance between a and b denoted as d(a,b) is a minimal amount of operations needed to transform number a into number b. For example, d(69,42)=3.

Keep in mind that our function d indeed has characteristics of the distance - for any positive ints a, b and c we get:

a) d(a,a)==0

b) d(a,b)==d(b,a)

c) the inequality of a triangle d(a,b)+d(b,c)>=d(a,c) is fulfilled.

You'll be given a sequence of positive ints a_1, a_2,...,a_n. For every a_i of them output such a_j (j!=i) that d(a_i, a_j) is as low as possible. For example, the sequence of length 6: {1,2,3,4,5,6} should output {2,1,1,2,1,2}.

This seems really hard to me. What I think would be useful is:

a) if a_i is prime, we are unable to make anything less than a_i (unless it's 1) so the only operation allowed is multiplication. Therefore, if we have 1 in our set, for every prime number d(this_number, 1) is the lowest.

b) also, for 1 d(1, any_prime_number) is the lowest.

c) for a non-prime number we check if we have any of its factors in our set or multiplication of its factors

That's all I can deduce, though. The worst part is I know it will take an eternity for such an algorithm to run and check all the possibilities... Could you please try to help me with it? How should this be done?

Answer 1

Indeed, you can represent any number N as 2^n1 * 3^n2 * 5^n3 * 7^n4 * ... (most of the n's are zeroes).

This way you set a correspondence between a number N and infinite sequence (n1, n2, n3, ...).

Note that your operation is just adding or subtracting 1 at exactly one of the appropriate sequence's places.

Let N and M be two numbers, and their sequences be (n1, n2, n3, ...) and (m1, m2, m3, ...). The distance between the two numbers is indeed nothing but |n1 - m1| + |n2 - m2| + ...

So, in order to find out the closest number, you need to calculate the sequences for all the input numbers (this is just decomposing them into primes). Having this decomposition, the calculation is straightforward.

---

Edit:
In fact, you don't need the exact position of your prime factor: you just need to know, which is the exponent for each of the prime divisors.

---

Edit:
this is the simple procedure for converting the number into the chain representation:

#include <map>

typedef std::map<unsigned int, unsigned int> ChainRepresentation;
// maps prime factor -> exponent, default exponent is of course 0

void convertToListRepresentation(int n, ChainRepresentation& r)
{
    // find a divisor
    int d = 2;

    while (n > 1)
    {
        for (; n % d; d++)
        {
            if (n/d < d) // n is prime
            {
                r[n]++;
                return;
            }
        }

        r[d]++;
        n /= d;
    }
}

---

Edit:
... and the code for distance:

#include <set>

unsigned int chainDistance(ChainRepresentation& c1, ChainRepresentation& c2)
{
    if (&c1 == &c2)
        return 0; // protect from modification done by [] during self-comparison

    int result = 0;

    std::set<unsigned int> visited;
    for (ChainRepresentation::const_iterator it = c1.begin(); it != c1.end(); ++it)
    {
        unsigned int factor = it->first;
        unsigned int exponent = it->second;
        unsigned int exponent2 = c2[factor];
        unsigned int expabsdiff = (exponent > exponent2) ?
                       exponent - exponent2 : exponent2 - exponent;
        result += expabsdiff;
        visited.insert(factor);
    }

    for (ChainRepresentation::const_iterator it = c2.begin(); it != c2.end(); ++it)
    {
        unsigned int factor = it->first;
        if (visited.find(factor) != visited.end())
            continue;
        unsigned int exponent2 = it->second;
        // unsigned int exponent = 0;
        result += exponent2;
    }

    return result;
}

Answer 2

For the given limits: 100_000 numbers not greater than a million the most-straightforward algorithm works (1e10 calls to distance()):

For each number in the sequence print its closest neighbor (as defined by minimal distance):

solution = []
for i, ai in enumerate(numbers):
    all_except_i = (aj for j, aj in enumerate(numbers) if j != i)
    solution.append(min(all_except_i, key=lambda x: distance(x, ai)))
print(', '.join(map(str, solution)))

Where distance() can be calculated as (see @Vlad's explanation):

def distance(a, b):
    """
    a = p1**n1 * p2**n2 * p3**n3 ...
    b = p1**m1 * p2**m2 * p3**m3 ...

    distance = |m1-n1| + |m2-n2| + |m3-n3| ...
    """
    diff = Counter(prime_factors(b))
    diff.subtract(prime_factors(a))
    return sum(abs(d) for d in diff.values())

Where prime_factors() returns prime factors of a number with corresponding multiplicities {p1: n1, p2: n2, ...}:

uniq_primes_factors = dict(islice(prime_factors_gen(), max(numbers)))

def prime_factors(n):
    return dict(multiplicities(n, uniq_primes_factors[n]))

Where multiplicities() function given n and its factors returns them with their corresponding multiplicities (how many times a factor divides the number without a remainder):

def multiplicities(n, factors):
    assert n > 0
    for prime in factors:
        alpha = 0 # multiplicity of `prime` in `n`
        q, r = divmod(n, prime)
        while r == 0: # `prime` is a factor of `n`
            n = q
            alpha += 1
            q, r = divmod(n, prime)
        yield prime, alpha

prime_factors_gen() yields prime factors for each natural number. It uses Sieve of Eratosthenes algorithm to find prime numbers. The implementation is based on gen_primes() function by @Eli Bendersky:

def prime_factors_gen():
    """Yield prime factors for each natural number."""
    D = defaultdict(list) # nonprime -> prime factors of `nonprime`
    D[1] = [] # `1` has no prime factors
    for q in count(1): # Sieve of Eratosthenes algorithm
        if q not in D: # `q` is a prime number
            D[q + q] = [q]
            yield q, [q]
        else: # q is a composite
            for p in D[q]: # `p` is a factor of `q`: `q == m*p`
                # therefore `p` is a factor of `p + q == p + m*p` too
                D[p + q].append(p)
            yield q, D[q]
            del D[q]

See full example in Python.

Output

2, 1, 1, 2, 1, 2

Answer 3

Without bounds on how large your numbers can be and how many numbers can be on the input, we can't really deduce it will take "an eternity" to complete. I am tempted to suggest the most "obvious" solution I can think of

1. Given the factorization of the numbers it is very easy to find their distance

   60 = (2^2)*(3^1)*(5^1)*(7^0)
   42 = (2^1)*(3^1)*(5^0)*(7^1)
   distance = 3
   

   Calculating this factorization using the naive trial division should take at most O(sqrt(N)) time per number, where N is the number being factorized.

2. Given the factorizations, you only have O(n^2) combinations to worry about, where n is the ammount of numbers. If you store all the factorizations so that you only compute them once, this step shouldn't take that long unless you have a really large amount of numbers.

---

You do wonder if there is a faster algorithm though. Perhaps it is possible to do some greatest common divisor trick to avoid computing large factorizations and perhaps we can use some graph algorithms to find the distances in a smarter way.

Answer 4

Haven't really thought this through, but it seems to me that to get from prime A to prime B you multiply A * B and then divide by A.

If you thus break the initial non-prime A & B into their prime factors, factor out the common prime factors, and then use the technique in the first paragraph to convert the unique primes, you should be following a minimal path to get from A to B.