GCD problem
Given a list of numbers, how do I find out the minimum number of numbers to remove to make sure that the gcd of the remaining numbers are greater than what it already is?
One way (which I haven't tried).
If your list of numbers isn't too big then prime-factorise every number (allowing for repeated primes) and count the number that each prime p is in, say C(pi), where pi is the ith occurrence of prime p. If C(pi) = N then this will be part of the gcd.
Then you need to remove all numbers that don't have the next commonest prime, so giving
N-max{ C(pi) : C(pi) < N }
If your list of numbers isn't too big then prime-factorise every number (allowing for repeated primes) and count the number that each prime p is in, say C(pi), where pi is the ith occurrence of prime p. If C(pi) = N then this will be part of the gcd.
Then you need to remove all numbers that don't have the next commonest prime, so giving
N-max{ C(pi) : C(pi) < N }
I don't fully get that.
10 20 40 (gcd 10)
2/5 2/5 2/5 (unique pfactors)
what do you remove here? (10, clearly, but how?)
does it need repeated factors? that is
2/5 2/2/5 2/2/2/5 but I still don't see what you meant.
10 20 40 (gcd 10)
2/5 2/5 2/5 (unique pfactors)
what do you remove here? (10, clearly, but how?)
does it need repeated factors? that is
2/5 2/2/5 2/2/2/5 but I still don't see what you meant.
The prime factors (with repeats) are
2 (C=3)
2 (C=2)
2 (C=1)
5 (C=3)
The largest value of C which isn't actually 3 is C=2 ... so you would remove 3-2 = 1 number: you aren't asked for which one it is.
2 (C=3)
2 (C=2)
2 (C=1)
5 (C=3)
The largest value of C which isn't actually 3 is C=2 ... so you would remove 3-2 = 1 number: you aren't asked for which one it is.
ah, I see. I was trying to actually ID the number(s) to remove. thanks!
Last edited on
So if the list is {6, 14, 17, 12}
{2^1 * 3, 2^1 * 7, 17, 2^2 * 3}
2 (C=2)
2 (C=1)
3 (C=2)
17 (C=1)
Largest value of C which isn't C=max is C=1, so remove 1 number?
Very nice that you don't actually need to know it's 17 in this case, if I'm doing the process correctly.
{2^1 * 3, 2^1 * 7, 17, 2^2 * 3}
2 (C=2)
2 (C=1)
3 (C=2)
17 (C=1)
Largest value of C which isn't C=max is C=1, so remove 1 number?
Very nice that you don't actually need to know it's 17 in this case, if I'm doing the process correctly.
Last edited on
Largest value of C which isn't 4 (signifying a factor that isn't in all numbers).
Your first 2 factor has C=3 (appears in 3 numbers: 6, 14 and 12).
4-3=1. You remove one number (the 17) so that that factor of 2 can enter the gcd. The gcd increases from 1 to 2.
Your first 2 factor has C=3 (appears in 3 numbers: 6, 14 and 12).
4-3=1. You remove one number (the 17) so that that factor of 2 can enter the gcd. The gcd increases from 1 to 2.
Last edited on
I love this, but it has an issue... factoring numbers is intractable; the prime factorization of 2 giant primes being our backbone for encryption techniques. Its not the size of the list, its the numbers in the list, a single pair of values in the list could break the whole thing.
Anyone see another approach that avoids the troubles for larger numbers? I don't see one yet..
Anyone see another approach that avoids the troubles for larger numbers? I don't see one yet..
Last edited on
Nah, it's only a hard problem if your input is an arbitrarily large number. Factorization of CPU words takes O(1) (the time is bounded by the size of the word).
The alternative would be to take out subsets of elements, which would take exponential time over the size of the list.
The alternative would be to take out subsets of elements, which would take exponential time over the size of the list.
Topic archived. No new replies allowed.