3
$\begingroup$

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

  • 0
    @PeterTaylor: As I understand it Chris is looking for which of an existing set of numbers is most similar, not which numbers are within a radius of 1 (those that differ by one prime).2011-10-24

2 Answers 2

1

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.

  • 0
    I don't re$a$lly think so, $b$ut knock yourself out: http://mym$a$thforum.com/viewtopic.php?f=40&t=242262011-10-27
1

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.