[Edu-sig] Mystery Number 6174
Tim Peters
tim.peters at gmail.com
Sun Jul 6 23:32:53 CEST 2008
[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
More information about the Edu-sig
mailing list