From the 1996 UF ACM High School Programming Competition

Number Chain

Yeah, you were caught skipping class. Ignoring that it was to go to a lecture by a Nobel laureate (What? Learn something?), your wonderful administration has decided to sentence you to hard labor in a chain gang. This isn't just any chain gang, though; this one is run by the math department.
You show up to find that you are to repeatedly calculate number chains, which are the repeating loops formed by subtracting the number with its digits sorted two different ways. Each worker has been given a set of numbers; any mistakes result in being given twice as many numbers on which to work. Naturally, you think, this kind of mindless work is perfect for a computer. No one notices when you slip out your laptop...

Problem Statement

Write a program to find the chain associated with any given number.

Start with the given positive integer. This is the first number in the chain. Sort the digits (of the base 10 number) into ascending order, and also in descending order. Subtract the ascending number from the descending number. This is the next number in the chain. Continue until you find a cycle.

Notes

Input will consist of a number of at most 6 digits, and the chain will repeat within 20 steps.

The output should show each step in finding the chain along with both the length until the chain is identified and the length of the chain.

Examples

Example 1:
Enter an integer: 56472
76542 - 24567 = 51975
97551 - 15579 = 81972
98721 - 12789 = 85932
98532 - 23589 = 74943
97443 - 34479 = 62964
96642 - 24669 = 71973
97731 - 13779 = 83952
98532 - 23589 = 74943
Length until repeat: 8
Length of chain: 4

Example 2:
Enter an integer: 893
983 - 389 = 594
954 - 459 = 495
954 - 459 = 495
Length until repeat: 3
Length of chain: 1

Grader's Test Data

Example 3:
Enter an integer: 345789
987543 - 345789 = 641754
765441 - 144567 = 620874
876420 - 24678 = 851742
875421 - 124578 = 750843
875430 - 34578 = 840852
885420 - 24588 = 860832
886320 - 23688 = 862632
866322 - 223668 = 642654
665442 - 244566 = 420876
876420 - 24678 = 851742
Length until repeat: 10
Length of chain: 7

Example 4:
Enter an integer: 932
932 - 239 = 693
963 - 369 = 594
954 - 459 = 495
954 - 459 = 495
Length until repeat: 4
Length of chain: 1

Example 5:
Enter an integer: 123456
654321 - 123456 = 530865
865530 - 35568 = 829962
998622 - 226899 = 771723
777321 - 123777 = 653544
655443 - 344556 = 310887
887310 - 13788 = 873522
875322 - 223578 = 651744
765441 - 144567 = 620874
876420 - 24678 = 851742
875421 - 124578 = 750843
875430 - 34578 = 840852
885420 - 24588 = 860832
886320 - 23688 = 862632
866322 - 223668 = 642654
665442 - 244566 = 420876
876420 - 24678 = 851742
Length until repeat: 16
Length of chain: 7

Example 6:
Enter an integer: 444
444 - 444 = 0
0 - 0 = 0
Length until repeat: 2
Length of chain: 1

Example 7:
Enter an integer: 69954
99654 - 45699 = 53955
95553 - 35559 = 59994
99954 - 45999 = 53955
Length until repeat: 3
Length of chain: 2

Solutions

Pascal solution by Michael Cariaso:: chain.pas