%I #15 Apr 06 2020 01:45:48
%S 0,53955,64308654,61974,86420987532
%N Consider the Kaprekar map x->K(x) described in A151949. Sequence gives the smallest number that belongs to a cycle of length n under repeated iteration of this map, or -1 if there is no cycle of length n.
%C No cycle of length 6 is presently known!
%C It is also known that a(7) = 420876, a(8) = 7509843, a(14) = 753098643.
%C From _Joseph Myers_, Aug 19 2009: (Start)
%C One does not need to consider every integer of n digits, only the sorted sequences of n digits (of which there are binomial(n+9, 9), so 28048800 for 23 digits). Then you only need to consider those sorted sequences of digits whose total is a multiple of 9, as the number and so the sum of its digits is always a multiple of 9 after the first iteration, which reduces the work by a further factor of about 9.
%C As a further refinement, the result of a single subtraction, if not zero, will have digit sequence of the form
%C d_1 d_2 ... d_k-1 9...9 9-d_k ... 9-d_2 9-d_1+1
%C where the values d_i are in the range 1 to 9 and the sequence of 9's in the middle may be empty.
%C From this form it follows that for any member of a cycle,
%C abs(number of 8's - number of 1's) + abs(number of 7's - number of 2's) +
%C abs(number of 6's - number of 3's) + abs(number of 5's - number of 4's) +
%C max(0, number of 0's - number of 9's) <= 4,
%C so given the numbers of 0's, 1's, 2's, 3's and 4's there is little freedom left in choosing the number of each remaining digit.
%C No further cycle lengths exist up to at least 140 digits. The only 4-cycles up to there are the ones containing 61974 and 62964, the only 8-cycles up to there are the ones containing 7509843 and 76320987633, the only 14-cycle up to there is the one containing 753098643. All the 7-cycles so far follow the pattern
%C 7-cycle: 420876
%C 7-cycle: 43208766
%C 7-cycle: 4332087666
%C 7-cycle: 433320876666
%C 7-cycle: 43333208766666
%C 7-cycle: 4333332087666666 ... (End)
%H R. J. Mathar, <a href="/A151959/a151959.txt">Maple code for A151949 and A151959</a>
%H Joseph Myers, <a href="/A099009/a099009.txt">List of cycles under Kaprekar map</a> (all numbers with <= 60 digits; cycles are represented by their smallest value)
%H <a href="/index/K#Kaprekar_map">Index entries for the Kaprekar map</a>
%e a(1) = 0: 0 -> 0.
%e a(2) = 53955: 53955 -> 59994 -> 53955 -> ...
%e a(3) = 64308654: 64308654 -> 83208762 -> 86526432 -> 64308654 -> ...
%e a(4) = 61974: 61974 -> 82962 -> 75933 -> 63954 -> 61974 -> ...
%Y A099009 gives the fixed points and A099010 gives numbers in cycles of length > 1.
%Y Cf. A151949.
%Y In other bases: A153881 (base 2), A165008 (base 3), A165028 (base 4), A165047 (base 5), A165067 (base 6), A165086 (base 7), A165106 (base 8), A165126 (base 9). [_Joseph Myers_, Sep 05 2009]
%K nonn,more,base
%O 1,2
%A _Klaus Brockhaus_ and _N. J. A. Sloane_, Aug 19 2009
%E The term a(3) = 64308654 was initially only a conjecture, but was confirmed by _Zak Seidov_, Aug 19 2009
%E a(4) = 61974 corrected by _R. J. Mathar_, Aug 19 2009 (we had not given the smallest member of the 4-cycle).
%E a(4) = 61974, a(7) = 420876, and a(8) = 7509843 confirmed by _Zak Seidov_, Aug 19 2009 (formerly the a(8) value was just an upper bound)
%E a(5) = 86420987532 and a(14) = 753098643 from _Joseph Myers_, Aug 19 2009. He also confirms the other values, and remarks that there are no other cycle lengths up to at least 140 digits.