Similarity of numbers Let's take two numbers A and B, and take their prime factorizations
$A=p_1^{a_1}\cdot p_2^{a_2}\cdot\dots \cdot p_n^{a_n}$
$B=p_1^{a'_1}\cdot p_2^{a'_2}\cdot\dots\cdot p_n^{a'_n}$
Now similarity of two numbers is simply
$$\sum_{i=1}^{\infty}|a_i-a'_i|$$
It's very easy to make it work and take similarity of two numbers using Eratosthenes sieve, but are there any properties of such "similarity"?
For example having numbers $A,B,C$ Is there other way to know to which number, number A is the most similar (excluding number A of course), then simply computing this similarity with every possible number?
Chris
 A: Computing sieve for high numbers are not efficient, so i assume that max value isn't higher than... 5 milions?
Anyway, let's have some set $S$ containing positive numbers not exceeding max value.
Easy observation: if two numbers are coprime then the similarity would be sum of $ai$ and $a'i$ for every $i$. So there is no point to match those two numbers, unless you have set $S$ with only coprime numbers.
Let's denote s(a,b) as similarity of two numbers.
Suprisingly, it holds triangle inequality e.g
$s(a,b)+s(a,c)>s(b,c)$
They are only simple observations, maybe even not leading to fast result.
A: As long as there are at least two primes in the set, the minimal distance is either 1 or 2.  So in that case it suffices to search for pairs with a distance of 1.  A simple algorithm that does not require factoring: for each number, check each larger number to see if it is divisible by the smaller.  If so, check if the quotient is prime (in which case you have found a pair with distance 1 and are done).  If the largest number divided by the small number is larger than the number of remaining numbers (or so), it may be faster to check if $n,2n,3n,\ldots$ are in the sequence (and then check divisibility/primality in the same way).
This is a reasonable test for small lists (up to a few hundred thousand, perhaps).
I've discussed this at some length with the question-asker off-site and received clarifications that way.
