Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
4  
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. –  anon Oct 24 '11 at 8:20
    
Do you really mean different $p$s in $B$? I mean, it seems that it should be $p_i$, not $p'_i$. –  lhf Oct 24 '11 at 10:04
    
yes, you are right, but it'll be harder to read it. –  Chris Oct 24 '11 at 10:12
    
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. –  Gerry Myerson Oct 24 '11 at 12:06
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). –  Peter Taylor Oct 24 '11 at 12:53

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
    
Maybe ot would be good if we could all see those clarifications? –  Gerry Myerson Oct 26 '11 at 22:08
    
I don't really think so, but knock yourself out: mymathforum.com/viewtopic.php?f=40&t=24226 –  Charles Oct 27 '11 at 15:04

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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