Task 2. Rats

Available Marks: 9

RATS (in this context) stands for Reverse, Add, Then Sort, applied to a positive decimal integer. It's the generating algorithm for an integer sequence that either diverges, or enters a reasonably short cycle. Consider the integer 180. Reversing the digits gives 081, or just 81. 180 + 81 = 261. Sorting the digits gives 126.

Continuing,

  126 +   621 =    747, sorted = 477
  477 +   774 =   1251, sorted = 1125
 1125 +  5211 =   6336, sorted = 3366
 3366 +  6633 =   9999, sorted = 9999
 9999 +  9999 =  19998, sorted = 18999
18999 + 99981 = 118980, sorted = 011889
11889 + 98811 = 110700, sorted = 000117
  117 +   711 =    828, sorted = 288
  288 +   882 =   1170, sorted = 117

Only a small number of different cycles can occur, we want to find them.

Your task

Write a program that identifies all cycles that occur for starting numbers less than 10000 (or 1000 for fewer marks). If any sequence element exceeds 1012, you may assume the sequence diverges. Complete answers depend on your computer using 64-bit arithmetic. In the event that your calculations use 32-bit arithmetic and overflow occurs, you will not be penalised provided the other cycles are reported correctly.

Your program's output should consist of one cycle on each line, ordered by period and then by the smallest member of the cycle. Each line should show three data items:

• the cycle period;
• the number of starting values that lead to that cycle; and
• the members of the cycle in order of occurrence, starting with the smallest member.

Period: 2, occurs 100 times, cycle: 117 288

Assessment

Full marks will be awarded for correctly identifying all cycles and displaying the details according to the requirements.

Deductions apply for incorrect identification, or if you don't cover all 9999 starting values, or for not displaying the data in the required order.