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


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?


  • 4
    $\begingroup$ You've essentially defined a nonstandard arithmetic metric on $\mathbb{N}$. You can speed up "similarity" calculations by reducing inputs by common divisors (enter Euclidean algorithm) but besides this I'm not sure you can do much more than brute factorization. $\endgroup$ – anon Oct 24 '11 at 8:20
  • $\begingroup$ Do you really mean different $p$s in $B$? I mean, it seems that it should be $p_i$, not $p'_i$. $\endgroup$ – lhf Oct 24 '11 at 10:04
  • $\begingroup$ yes, you are right, but it'll be harder to read it. $\endgroup$ – Krzysztof Lewko Oct 24 '11 at 10:12
  • $\begingroup$ Better it should be hard to read than it should be nonsense, as it is now. You know, it's not the case that every pair of integers has the same number of distinct prime factors. $\endgroup$ – Gerry Myerson Oct 24 '11 at 12:06
  • 1
    $\begingroup$ To address the example, multiply $A$ by any prime (or divide by any prime factor) to get a number with minimal "similarity". (The name is very counterintuitive). $\endgroup$ – Peter Taylor Oct 24 '11 at 12:53

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.


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


They are only simple observations, maybe even not leading to fast result.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.