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.

Possible Duplicate:
Computing GCD of all permutations (of the digits) of a given number.

How can we find the greatest common divisor (GCD) of all numbers that can be obtained by permuting the digits in the given number?

Please suggest a feasible algorithm.

share|improve this question
2  
Possible duplicate:math.stackexchange.com/questions/8943/… –  Quixotic Feb 20 '11 at 12:50
add comment

marked as duplicate by Ross Millikan, Arturo Magidin, Akhil Mathew Mar 18 '11 at 13:49

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

2 Answers

First, assume not all digits are the same (since then this problem is trivial). Now note what happens if you exahcnge the two least significant digits. You either add or subtract a certain number a 2-digit one). Now, if you have a divisor in both the number and the one obtained by exchanging these digits, then this is also a divisor in this 2-digit number, so you have severely reduced the problem. You can do this for any two distinct digits in the number, thus getting a set of -digit numbers, the gcd of the permutations of the original number will divide the gcd of these numbers. (note that all these 2-digit number will be divisible by 9, so you need to check if the original number is divisible by 9, but this property is not changed by permuting the number anyway). Now the problem has been reduced to checking among some 2-digit numbers, but we might not be done yet, since the gcd of the permutations of the original numbers might be even smaller. I will think a bit about how one can easily make sure to get the actual gcd.

share|improve this answer
add comment

This has a weaker version which might give some hint as far as I am concerned.
In any case, thanks for paying attention and if I make some mistakes, please inform me.

share|improve this answer
1  
That's a bit of too much mathematics for me :| –  Quixotic Feb 16 '11 at 10:19
1  
Maybe you can view numbers as values of polynomials at 10 with coefficients in the residue class ring $Z/(10)$, sorry for being unclear before. –  awllower Feb 16 '11 at 13:26
add comment

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