[seqfan] Re: Mini-max numbers

[Joseph S. Myers]

On Fri, 10 May 2013, Vladimir Shevelev wrote:

> Let, for n>=3, N be n-digit number such that the first zeros are allowed 
> but not all digits are the same. Let consider digits of N in 
> non-increasing order and the corresponding number denote by N_max; after 
> that we consider digits of N in non-decreasing order and the 
> corresponding number denote by N_min. If N_max-N_min=N, then we call N a 
> mini-max number of cycle 1; if N_max-N_min=N_1 which differs of N, but 
> (N_1)_max-(N_1)_min=N, then we call N a mini-max number of cycle 2, etc. 
> By handy, I found the following numbers:
> If n=3, N=495 is a mini-max number of cycle 1. Indeed, 954-459=495;
> If n=4, N=6174 is a mini-max number of cycle 1. Indeed, 7641-1467=6174;
> If n=5, N=53955 is a mini-max number of cycle 2, since 
> N_1=95553-35559=59994 and N_2=99954-45999=53955=N;
> If n=6, N=840852 is a mini-max number of cycle 7, since 
> N_1=885420-024588=860832;  N_2=886320-023688=862632;
> N_3=866322-223668=642654; N_4=665442-244566=420876; 
> N_5=876420-024678=851742; N_6=875421-124578=750843; 
> N_7=875430-034578=840852=N.
> It is interesting to find for every n the set of mini-max numbers with 
> their cycles. Are mini-max numbers known, maybe, under another name?

Look up sequences related to the "Kaprekar map".  (That's slightly 
different in that the number of digits goes down if the difference would 
have a leading zero when interpreted as an n-digit number.  But you don't 
get anything interesting by allowing leading zeros.)

These were discussed a bit on seqfan in August 2009, but then the 
discussion moved off-list.  The following are observations of mine from 
that time:

Theorems:

* In base 2, all cycles are fixed points and a complete classification
of fixed points is easy; they are numbers of the form 2^n - 2^(n-k) -
2^k + 1 for 1 < k < n-1 (note that k and n-k yield the same fixed
point, which results from any n-digit number with k or n-k 1s in it).

* In any base b, there are finitely many "types" of c-cycle for any
fixed constant c: at most O((3 * 2^(b+1))^c) such types if I've
calculated correctly.  A type is given by O(bc) linear equations and
inequalities in 1+ceil(b/2) variables, whose coefficients are O(2^c);
to go from types to the number of n-digit c-cycles you need to count
(as a function of n probably given by a generating function) the
number of lattice points with each n-coordinate inside a possibly
empty convex body described by those equations and inequalities (which
does always give a rational generating function; the question is just
the complexity of calculating it).  This method would actually find
and count the number of n-digit numbers that are in a cycle of length
dividing c, so to count c-cycles the numbers in shorter cycles need
removing and the result needs dividing by c.  Certainly this seems
infeasible for determining whether there are 6-cycles in base 10;
since the calculations needed for each case are quite complicated,
even using it for 4-cycles in base 4 seems of borderline feasibility.

* In any even base b > 2, consider the set of n-digit numbers that are
members of cycles and satisfy "number of digits (b-1) - number of
digits 0 = o(n)".  Almost all numbers in that set are in a cycle of
length exactly A003558(b/2 - 1), and so almost all cycles containing
at least one number with that property have that length.

Conjectures:

* In any odd base, there are arbitrarily long cycles.  A stronger
conjecture would be that all cycle lengths are present.

* In any even base, there are only finitely many cycle lengths and
there exists an algorithm to determine them (or equivalently to
produce an upper bound on cycle length).

* In any even base b > 2, almost all n-digit numbers in cycles are in
a cycle of length exactly A003558(n/2 - 1) (i.e., the condition above
about not having many more b-1 digits than 0 digits is not necessary)
and so almost all cycles of n-digit numbers have that length.

I hope there are much better ways of classifying and counting fixed
points in any base than considering O(2^b) cases, but don't have a
specific conjecture about this.

-- 
Joseph S. Myers
jsm at polyomino.org.uk