This problem was posed by Pierre Lescanne in the Issue 23 of Inforum (December 1995), a local publication at Inria-Lorraine - Crin in Nancy. The statement of the problem is the following: for a given n>=2, consider the set E of all n-digits numbers with at least two different digits [there are 10^n-10 such numbers] and the following function f from E to E. Given a number x, first sort its digits in descending order, obtaining a, then sort its digits in ascending order, obtaining b, then subtract b from a, obtaining a new n-digit number which is denoted f(x).

For example for n=4, with x=6019, we have a=9610, b=0169, therefore f(x) = 9610 - 0169 = 9441. What is interesting for n=4 is that if we iterate f starting from any of the 9990 numbers in E, we end on the number 6174 which is a fixpoint. But such a fixpoint does not always exist. For n=5 there is no fixpoint.

For general n, we can say the following: as f is a function over a finite set, its graph is as follows. It is a set of connected components, each component being a cycle on which are planted some trees. For all numbers of a connected component, the iteration of the function ends and loops on the corresponding cycle, which we call a limit cycle. To reduce the search, we can use the following remarks made by Pierre Lescanne: we can first consider only number with digits in descending order, because f(x)=f(a)=f(b) with the notations above. Secondly, we can restrict ourselves to number with the right half of digits being zero. For example for n=4 we can consider only numbers of the form ij00. This is due to the fact that if 9>=i>=j>=k>=l>=0, then f(1000*i+100*j+10*k+l)=f(1000*(i-l)+100*(j-k)). This reduces the search to 54 cases for n=4. Using his program Adocs, Francois Bertault has drawn the graph of f for n= 4, 5, 6, 7, 8, 9.

Christopher Lynch proved that:
(A) 6{3^j}17{6^j}4 is a fixpoint for j>=0,
(B) 5^{k-1} 4 9^{k} 4^{k-1} 5 is a fixpoint for k>=1,
(C) 9^k 7 5 3^j 0 8 6^j 4 2 0^{k-1} 1 is a fixpoint for j>=0, k>=1,
(D) 8 6 4 3^j 1 9 7 6^j 5 3 2 is a fixpoint for j>=0.
(A) says that there are fixed points for all even n greater than or equal to 4. (B) says that there are fixed points for all n divisible by 3. (D) says that there are fixed points for all odd numbers greater than or equal to 9. Therefore from (A) and (D), it follows that there is at least one fixpoint for all n>=8. The study of the remaining cases (see below) shows that the only values of n for which there is no fixpoint are n=2, n=5 and n=7.

Christopher Lynch proved also the following theorem:
Even Case. Let x_1,x_2,...,x_m be a number that appears as a non-first element in some sequence. If m = 2n for some n, then there is a k, with 1 < k <= n such that (a) if k < i < (m+1)-k then x_i = 9. (b) if i <= k then x_i + x_{(m+1)-i} = 9 if i <> 1 and i <> k, x_i + x_{(m+1)-i} = 10 if i = 1 and i <> k, x_i + x_{(m+1)-i} = 8 if i <> 1 and i = k, x_i + x_{(m+1)-i} = 9 if i = 1 and i = k.
Odd Case. Let x_0,x_1,...,x_m be a number that appears as a non-first element in some sequence. If m = 2n for some n, then there is a k, with 1 < k < n such that (a) if k < i < m-k then x_i = 9. (b) if i <= k then x_i + x_{m-i} = 9 if i <> 1 and i <> k, x_i + x_{m-i} = 10 if i = 1 and i <> k, x_i + x_{m-i} = 8 if i <> 1 and i = k, x_i + x_{m-i} = 9 if i = 1 and i = k.

As a corollary of this theorem, for odd n, the middle digit of fixpoints or points in limit cycles is always 9. Also, the fixpoints and points in limit cycles are equal to 0 mod 9.

For n=2, there is only one limit cycle, namely [09, 81, 63, 27, 45].

For n=5, there are three limit cycles, one of length 2, namely [53955, 59994], for example when we start from 5, and two of length 4, namely [83952, 74943, 62964, 71973] and [63954, 61974, 82962, 75933].

For n=6 there are two fixpoints, 631764 and 549945, and one limit cycle of length 7, namely [420876, 851742, 750843, 840852, 860832, 862632, 642654].

For n=7, there is only one limit cycle, of length 8, namely [8429652, 7619733, 8439552, 7509843, 9529641, 8719722, 8649432, 7519743].

For n=8, there are two fixpoints, 63317664 and 97508421, one limit cycle of length 3, namely [83208762, 86526432, 64308654] and one limit cycle of length 7, namely [86326632, 64326654, 43208766, 85317642, 75308643, 84308652, 86308632].

For n=9, there are two fixpoints, 864197532 and 554999445, and one limit cycle of length 14, namely [873197622, 865395432, 753098643, 954197541, 883098612, 976494321, 874197522, 865296432, 763197633, 844296552, 762098733, 964395531, 863098632, 965296431].

For n=10, there are three fixpoints, 9975084201, 9753086421 and 6333176664, four limit cycles of length 3, namely [9775084221, 9755084421, 9751088421], [6433086654, 8332087662, 8653266432], [8732087622, 8655264432, 6431088654] and [8321088762, 8765264322, 6543086544], and one limit cycle of length 7, namely [8433086652, 8633086632, 8633266632, 6433266654, 4332087666, 8533176642, 7533086643].

Addendum from Christopher Lynch (2 Feb 1996):
It is possible to generalize the problem for base b (previously we were only considering base 10). Given a base b, I have an algorithm to schematize all the fixed points for base b. The algorithm works by creating exponentially many (i.e. 2^b) systems of equations. Each system of equations has b equations and b variables, with coefficients of 0, 1, or 2. Each system of equations with a solution represents a schematization of a set of fixed points. Together, this represents all the fixed points for base b.

I ran the algorithm by hand for all the bases up to 5.. The answers are:

Base 2: {1^k-1}0{1^j}{0^k-1}1 for j>=0, k>=1

Base 3: {2^j}{1^k-1}0{2^k}{1^k}{0^j-1}1 for j,k>=1

```Base 4: {3^i}{2^j}{1^k-1}0{3^j}{2^k}{1^j}{0^i-1}1  for i,k>=1 j>=0
{2^i-1}1{3^i}{1^i-1}2                      for i>=1
```
```Base 5: {4^j}{3^k}{2^k}{1^k-1}0{4^k}{3^k}{2^k}{1_k}{0^j-1}1 for j,k>=1
3032
13
```
I think it would be possible to program this and get the answer for base 10. The number of cases would be in the thousands.