login
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.
18

%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.