[Edu-sig] Mystery Number 6174

[Tim Peters]

[kirby urner]
> Yutaka Nishiyama has this interesting article in the March 2006 issue
> of Plus, entitled 'Mysterious number 6174'.
>
> The theorem in this article is as follows: any 4-digit positive
> integer, stipulating all 4 digits *not* be the same one, may be
> distilled to 6174 by the following
> process: extract the largest and smallest two integers from the 4
> digits and subtract the smaller from the larger, and repeat as
> necessary.
>
>>>> funtopic.converge()
> 2283: 8322 - 2238 == 6084
> 6084: 8640 - 0468 == 8172
> 8172: 8721 - 1278 == 7443
> 7443: 7443 - 3447 == 3996
> 3996: 9963 - 3699 == 6264
> 6264: 6642 - 2466 == 4176
> 4176: 7641 - 1467 == 6174

> ...

> Here's one way to test the result.  Think of a different way?

I'd rather write code to /find/ that result ;-)  See below for one way
to do that.


> def somenum(n = 4):
>    digits = range(10)
>    ans = []
>    good = False # no exit pass (yet)
>
>    while True:
>
>        for i in range(n):
>            ans.append(choice(digits)) # pick any n digits
>
>        firstdigit = ans[0]
>        # not much chance all digits the same
>        # compare first to rest, pass test on first
>        # exception
>        for i in range(1,n+1):
>            if firstdigit != ans[i]:
>                good = True  # exit pass
>                break
>
>        if good:  break # has exit pass
>
>    return "".join([str(i) for i in ans])

Just noting that this part is simpler as (and fixing n at 4 for simplicity):

def somenum():
    import random
    while True:
        n = random.randrange(10000)
        if n % 1111:
            return "%04d" % n

Note that all 4 digits are the same if and only if n is a multiple of 1111.


> ...

To find a result like this, you have to analyze the cycles that arise
when iterating

    n = f(n)

for a suitable function `f`.  Function repeat() below does that pretty
generally, assuming only that the values `n` can be set members and
dict keys.  The NDigits class drives repeat() with the right kind of
stuff for this specific problem.

# Repeat
#     n = iterate(n)
# until it falls into a cycle (some value of n is seen again). For all
# n generated, n2repeat[n] is set to that repeated value.  In addition,
# if some n along the way is already a key in n2repeat, the iteration
# stops early, and n2repeat[n] is used as the repeated value.
def repeat(n, iterate, n2repeat):
    sofar = set()
    while n not in n2repeat and n not in sofar:
        sofar.add(n)
        n = iterate(n)
    if n in n2repeat:
        repeated = n2repeat[n]
    else:
        assert n in sofar
        repeated = n
    for n in sofar:
        n2repeat[n] = repeated

class NDigits(object):
    def __init__(self, ndigits):
        self.ndigits = ndigits
        # Format to convert integer to string with `ndigits` digits,
        # zero-filled (if needed) on the left.
        self.format = "%0" + str(ndigits) + "d"

    def step(self, n):
        lo = sorted(n)
        hi = "".join(reversed(lo))
        lo = "".join(lo)
        return self.format % (int(hi) - int(lo))

    def tryall(self):
        n2repeat = {}
        fmt = self.format
        for n in xrange(10**self.ndigits):
            n = fmt % n
            repeat(n, self.step, n2repeat)
        repeat2ns = dict((r, 0) for r in set(n2repeat.itervalues()))
        for r in n2repeat.itervalues():
            repeat2ns[r] += 1
        for r in sorted(repeat2ns):
            print r, "reached by", repeat2ns[r], "inputs"

Finally, a bit of code to drive that, for number of digits from 1 through 7:

for ndigits in range(1, 8):
    print "trying", ndigits, "digits"
    driver = NDigits(ndigits)
    driver.tryall()
    print

Perhaps not surprisingly, the output shows that 2-digit integers have
an "attractor" (09) too, and also 3-digit integers (495).  However 5-
and 6-digit integers do not have a (unique) attractor.  And that made
the output for 7-digit integers surprising indeed!

trying 1 digits
0 reached by 10 inputs

trying 2 digits
00 reached by 10 inputs
09 reached by 90 inputs

trying 3 digits
000 reached by 10 inputs
495 reached by 990 inputs

trying 4 digits
0000 reached by 10 inputs
6174 reached by 9990 inputs

trying 5 digits
00000 reached by 10 inputs
53955 reached by 3190 inputs
63954 reached by 48480 inputs
74943 reached by 48320 inputs

trying 6 digits
000000 reached by 10 inputs
549945 reached by 1950 inputs
631764 reached by 62520 inputs
851742 reached by 935520 inputs

trying 7 digits
0000000 reached by 10 inputs
8429652 reached by 9999990 inputs