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

  • 4
    You've essentially defined [a nonstandard arithmetic metric](http://arxiv.org/abs/0906.0632) 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.2011-10-24
  • 0
    Do you really mean different $p$s in $B$? I mean, it seems that it should be $p_i$, not $p'_i$.2011-10-24
  • 0
    yes, you are right, but it'll be harder to read it.2011-10-24
  • 0
    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.2011-10-24
  • 0
    Can you help me then ? How to write it nicely?2011-10-24
  • 0
    @Gerry "it's not the case that every pair of integers has the same number of distinct prime factors" - True, but perhaps that obstacle can be overcome by allowing some of the $a_i$ and $a_i'$ to be zero, so that $\{ p_1, \ldots, p_n \}$ can be taken to be the set of prime numbers that divide either of the numbers. (EDIT: I do think $p_i'$ should really be $p_i$ though.)2011-10-24
  • 0
    You are right, i've corrected it.2011-10-24
  • 1
    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).2011-10-24
  • 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
    Maybe ot would be good if we could all see those clarifications?2011-10-26
  • 0
    I don't really think so, but knock yourself out: http://mymathforum.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.