[seqfan] Re: Mini-max numbers

[Vladimir Shevelev]

Thank you, Joseph, for your theorems and conjectures and for key words "Kaprekar map". Using them, I found paper 
http://mathworld.wolfram.com/KaprekarRoutine.html and several interesting references there.
 
Consider also the following Kaprekar-like map. To every even digit of N we add 1. Denote new number by [N]. 
Let N_1=[N]_max-[N]_min. If [N_1]=[N], we say that [N] is Kaprekar-like number of cycle 1, otherwise, let N_2 =
[N_1]_max-[N_1]_min. If [N_2]=[N], we say that [N] is Kaprekar-like number of cycle 2, etc.
 
By handy, I found the following  Kaprekar-like numbers with odd digits for n=2,3,4,5,6:  37 of cycle 1, 595 of cycle 2, 7175 of cycle 1, 75935 of cycle 4, 539957 of cycle 5.
 
Best regards,
Vladimir



----- Original Message -----
From: "Joseph S. Myers" <jsm at polyomino.org.uk>
Date: Friday, May 10, 2013 10:16
Subject: [seqfan] Re: Mini-max numbers
To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>

> 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
> 
> _______________________________________________
> 
> Seqfan Mailing list - http://list.seqfan.eu/
> 

 Shevelev Vladimir‎