# Computing GCD of all permutations (of the digits) of a given number

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.

-
The result of permuting the digits of $n$ will always result in a number that is congruent to $n$ modulo $9$ and modulo $3$. – Arturo Magidin Nov 4 '10 at 19:44
@Arturo Magidin: Thank you, this is indeed a very good observation but how can I use this here ? – Quixotic Nov 5 '10 at 7:57
well, not for much, but it either gives or discards a possible factor of the GCD; for $N=345$, we could immediately see that $3$ was a factor of the GCD but $9$ was not, for instance. – Arturo Magidin Nov 5 '10 at 15:59

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.

-
This is a great answer, you get my +1 easily. My answer fleshes yours out a bit more, but more work remains. – Charles Nov 5 '10 at 2:44
Okay, I didn't understand what you meant by largest digit that is different from it I think you meant : first we need to sort the digits of the number then swap the last with the first one (the max and min) if we call this as b now we need to compute gcd(a,abs(b-a)) for the correct answer ? – Quixotic Nov 5 '10 at 7:54
I meant something like this: if a is, say, 1133799, then switch the last digit with a 7. But I realized when thinking about it later (and Charles points out in his answer) that we can do even better. For any two distinct digits m and n, we can form two numbers -- one that ends in mn, and one that ends in nm, with the rest of the number the same. For example, with the digits above, we get 1133997 - 1133979 = 18. So the gcd divides 18, and this cuts down our work a lot. – Gabe Cunningham Nov 5 '10 at 11:10
Right. If there are n digits, we can use all n(n-1)/2 combinations. I attempted in my answer to handle the common cases first, so we could avoid sorting the digits if possible. – Charles Nov 5 '10 at 13:07
So the answer boils down to gcd of (1133997,1133997-1133979). – Quixotic Nov 7 '10 at 13:41

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?

-
I think I can put it further by the answer here which is posted as an answer by @Mark Bennet. As far as I am concerned, this post is similar to the answer by @Ross Millikan and moreover exhausts other situations. Please inform me of any latest development, thanks very much. – awllower Feb 21 '11 at 13:47

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]]

-
I'd use IntegerDigits[] instead, so you don't need the [[1]]. :) – J. M. Nov 4 '10 at 22:31
@J.M.: Thanks. I don't really use Math'ca, so I have a lot to learn there. – Charles Nov 5 '10 at 2:42
That Sloane's sequence has 19 instead of 1,9. I tried registering, so I can edit it, but I've got bored of waiting for the confirmation email. Anybody else want to do it? – TonyK Mar 18 '11 at 11:45

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))

-