[Edu-sig] Mystery Number 6174

[Tim Peters]

[Tim Peters]
>>> ...
>>> trying 7 digits
>>> 0000000 reached by 10 inputs
>>> 8429652 reached by 9999990 inputs

[Massimo Di Pierro]
>> This is interesting
>>
>> The probability of a single fixed point in in 10**7 numbers is quite small.

[Tim]
> [elaborates, but doesn't really explain anything ;-)]

I think a key point here is to realize how few inputs there "really"
are.  For example, there are 5040 (== factorial(7)) 7-digit numbers
that all sort to 1234567.  So all of those lead to the same sequence
of iterates, after the first position.  In fact, across the 10 million
7-digit numbers, there are fewer than 12 thousand unique values
remaining after sorting.

A fancier version of the program I posted exploits that, generating
(just) the unique values directly.  This vastly slashes computation
costs, allowing quick computation of what happens.  The output makes
what's happening a lot clearer (well, to me ;-)).  I'll cut it off
here after the output for 12-digit inputs;

trying 1 digits
10 essentially unique inputs
10 inputs (10 unique) end in cycle:
    0

trying 2 digits
55 essentially unique inputs
10 inputs (10 unique) end in cycle:
    00
90 inputs (45 unique) end in cycle:
    09
    81
    63
    27
    45

trying 3 digits
220 essentially unique inputs
10 inputs (10 unique) end in cycle:
    000
990 inputs (210 unique) end in cycle:
    495

trying 4 digits
715 essentially unique inputs
10 inputs (10 unique) end in cycle:
    0000
9,990 inputs (705 unique) end in cycle:
    6174

trying 5 digits
2,002 essentially unique inputs
10 inputs (10 unique) end in cycle:
    00000
3,190 inputs (108 unique) end in cycle:
    53955
    59994
48,320 inputs (1,004 unique) end in cycle:
    74943
    62964
    71973
    83952
48,480 inputs (880 unique) end in cycle:
    63954
    61974
    82962
    75933

trying 6 digits
5,005 essentially unique inputs
10 inputs (10 unique) end in cycle:
    000000
1,950 inputs (30 unique) end in cycle:
    549945
62,520 inputs (352 unique) end in cycle:
    631764
935,520 inputs (4,613 unique) end in cycle:
    851742
    750843
    840852
    860832
    862632
    642654
    420876

trying 7 digits
11,440 essentially unique inputs
10 inputs (10 unique) end in cycle:
    0000000
9,999,990 inputs (11,430 unique) end in cycle:
    8429652
    7619733
    8439552
    7509843
    9529641
    8719722
    8649432
    7519743

trying 8 digits
24,310 essentially unique inputs
10 inputs (10 unique) end in cycle:
    00000000
599,536 inputs (300 unique) end in cycle:
    63317664
2,371,040 inputs (321 unique) end in cycle:
    97508421
48,247,316 inputs (12,051 unique) end in cycle:
    86526432
    64308654
    83208762
48,782,098 inputs (11,628 unique) end in cycle:
    86326632
    64326654
    43208766
    85317642
    75308643
    84308652
    86308632

trying 9 digits
48,620 essentially unique inputs
10 inputs (10 unique) end in cycle:
    000000000
34,440 inputs (30 unique) end in cycle:
    554999445
51,389,136 inputs (2,388 unique) end in cycle:
    864197532
948,576,414 inputs (46,192 unique) end in cycle:
    865296432
    763197633
    844296552
    762098733
    964395531
    863098632
    965296431
    873197622
    865395432
    753098643
    954197541
    883098612
    976494321
    874197522

trying 10 digits
92,378 essentially unique inputs
10 inputs (10 unique) end in cycle:
    0000000000
4,306,680 inputs (264 unique) end in cycle:
    6333176664
41,045,760 inputs (169 unique) end in cycle:
    9975084201
558,293,820 inputs (3,582 unique) end in cycle:
    9775084221
    9755084421
    9751088421
644,450,820 inputs (5,718 unique) end in cycle:
    9753086421
1,058,345,520 inputs (9,004 unique) end in cycle:
    8765264322
    6543086544
    8321088762
1,291,432,626 inputs (13,110 unique) end in cycle:
    8655264432
    6431088654
    8732087622
2,476,855,476 inputs (21,583 unique) end in cycle:
    8633086632
    8633266632
    6433266654
    4332087666
    8533176642
    7533086643
    8433086652
3,925,269,288 inputs (38,938 unique) end in cycle:
    8653266432
    6433086654
    8332087662

trying 11 digits
167,960 essentially unique inputs
10 inputs (10 unique) end in cycle:
    00000000000
7,444,117,296 inputs (9,432 unique) end in cycle:
    86431976532
30,759,712,236 inputs (53,134 unique) end in cycle:
    87331976622
    86542965432
    76320987633
    96442965531
    87320987622
    96653954331
    86330986632
    96532966431
61,796,170,458 inputs (105,384 unique) end in cycle:
    88431976512
    87641975322
    86541975432
    86420987532
    96641975331

trying 12 digits
293,930 essentially unique inputs
10 inputs (10 unique) end in cycle:
    000000000000
697,950 inputs (30 unique) end in cycle:
    555499994445
57,413,664 inputs (312 unique) end in cycle:
    633331766664
556,839,360 inputs (169 unique) end in cycle:
    999750842001
6,771,885,120 inputs (529 unique) end in cycle:
    997530864201
10,397,350,260 inputs (1,632 unique) end in cycle:
    997750842201
    997550844201
    997510884201
14,186,684,160 inputs (2,281 unique) end in cycle:
    977750842221
    975550844421
    975110888421
23,752,825,668 inputs (12,423 unique) end in cycle:
    865552644432
    643110888654
    877320876222
28,903,840,680 inputs (5,939 unique) end in cycle:
    975330866421
35,851,244,880 inputs (8,636 unique) end in cycle:
    975510884421
    977510884221
    977550844221
37,978,377,360 inputs (12,157 unique) end in cycle:
    876552644322
    654310886544
    873210887622
76,745,507,520 inputs (22,871 unique) end in cycle:
    877652643222
    655430865444
    832110888762
91,728,976,482 inputs (19,930 unique) end in cycle:
    977530864221
    975530864421
    975310886421
124,802,255,728 inputs (36,177 unique) end in cycle:
    876532664322
    654330866544
    833210887662
125,925,387,258 inputs (41,233 unique) end in cycle:
    865532664432
    643310886654
    873320876622
171,533,411,258 inputs (52,153 unique) end in cycle:
    863330866632
    863332666632
    643332666654
    433320876666
    853331766642
    753330866643
    843330866652
250,807,302,642 inputs (77,448 unique) end in cycle:
    865332666432
    643330866654
    833320876662