Consider a number say $N = 345$.
The permutations are : {{3, 4, 5}, {3, 5, 4}, {4, 3, 5}, {4, 5, 3}, {5, 3, 4}, {5, 4, 3}}
The GCD of all of them is 3 which is the answer. Please suggest a suitable approach for this problem.
Consider a number say $N = 345$.
The permutations are : {{3, 4, 5}, {3, 5, 4}, {4, 3, 5}, {4, 5, 3}, {5, 3, 4}, {5, 4, 3}}
The GCD of all of them is 3 which is the answer. Please suggest a suitable approach for this problem.
I've gotta run, so I can't flesh this out quite as much as I want, but here's a start.
Note that gcd(a, b) = gcd(a, b-a). Thus, if a and b are close to each other, they must have a small gcd.
In particular, consider a number N. Let a consist of all of the digits of N, sorted in ascending order. Now switch the last digit with the largest digit that is different from it, and call this new number b. Then b-a will be "small". I suspect it's possible to refine this to get a quick answer.
First, if all the digits are the same, there is only one number and that is the GCD. As was pointed out before, if 3 or 9 is a factor of one permutation it will be a factor of them all. Otherwise, imagine swapping just the ones and tens digit when they are different. The GCD of these two has to divide $100a+10b+c-100a+10c+b=9(b-c)$ where $b$ and $c$ are single digits. For the GCD of all the numbers to have a factor 2, all the digits must be even. For the GCD to have a factor 4, all the digits must be 0, 4, or 8 and for 8 they must be 0 or 8. Similarly for 5 and 7. Finally, the GCD will be 27 if all the digits are 0,3,6, or 9 and 27 divides one permutation and 81 if all the digits are 0 or 9 and 81 divides one permutation. Can you prove the last assertion?
This is Sloane's A069652. The best way I can think of is to actually permute the digits and calculate -- though checking for 2, 5, and 3/9 first in the obvious way (all digits even, all digits 0 or 5, all digits add to a multiple of 3/9) in hopes that the rest of the number will have gcd 1 and terminate early that way. Storing numbers in BCD (or as a vector of digits, or as a byte array) would make this fastest, I imagine.
Edit: Building on Gabe's answer, pick two distinct digits m and n in the number, if they exist. (If not, return the number.) The gcd divides 9(m-n). Together with the 2/3/5/9 trick, this should determine most numbers quickly.
Otherwise, continue choosing digits until you're gone through all combinations. The hardest case is numbers where all digits are divisible by 3 and the sum of digits is divisible by 9; you must actually work with the numbers in this case to determine what power of 3 divides the number (at least 2).
In any case here's some naive Math'ca code in case someone wants to check their implementation.
f[n_] := GCD @@ FromDigits /@ Permutations[IntegerDigits[n]]
In the case you have given you just need to note that the sum of the digits of 345 is divisible by 3. More generally, my first thoughts are that there is no straightforward answer.
There are of course lots of cases such as numbers like, 198, 5505005, 777777777, 4848448, etc where we can say something more easily.
If n|100a+10b+c then all permutations are multiples of n iff n|99(x-y) for all combinations of digits x,y. If n|1000a+100b+10c+d then all permutations are multiples of n iff n|999(x-y) for all combinations of digits x,y.And so on with m-1 9s if m is the number of digits of the number to be permuGCDed. If GCD(n,999...)=1 then the permutations are not all multiples of n unless a,b... are all multiples of n (0 is counted as a multiple of n). If GCD(n,999...)=t, all permutations will be a multiple of t.
GCD of all permutations = LCM(GCD(9999...,any one of the permutations), GCD(all the digits))