[seqfan] Re: Mini-max numbers
shevelev at bgu.ac.il
Sat May 11 13:34:08 CEST 2013
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.
----- 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,
> > 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
> 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
> discussion moved off-list. The following are observations
> of mine from
> that time:
> * 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.
> * 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/
More information about the SeqFan