Re: [Edu-sig] Mystery Number 6174
[Tim Peters] >>> ... >>> trying 7 digits >>> 000 reached by 10 inputs >>> 8429652 reached by 990 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: 9,990 inputs (705 unique) end in cycle: 6174 trying 5 digits 2,002 essentially unique inputs 10 inputs (10 unique) end in cycle: 0 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: 00 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: 000 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: 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: 0 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: 00 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: 000 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: 697,950 inputs (30 unique) end in cycle: 55544445 57,413,664 inputs (312 unique) end in cycle: 6174 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: 99
Re: [Edu-sig] Mystery Number 6174
[Massimo Di Pierro] > This is interesting [Tim Peters] >> trying 7 digits >> 000 reached by 10 inputs >> 8429652 reached by 990 inputs [Massimo] > The probability of a single fixed point in in 10**7 numbers is quite small. Well, note that the program was looking for cycles, not for fixed points. In fact, the only 7-digit fixed point is 000. 8429652 is not a fixed point, but turns out it's part of a cycle everything other than multiples of 111 eventually falls into: 8429652 -> 7619733 -> 8439552 -> 7509843 -> 9529641 -> 8719722 -> 8649432 -> 7519743 -> 8429652 It may be easier to think about the 2-digit results, where again 00 is the only fixed point, but everything other than multiples of 11 eventually falls into a cycle containing 09: 09 -> 81 -> 63 -> 27 -> 45 -> 09 ___ Edu-sig mailing list Edu-sig@python.org http://mail.python.org/mailman/listinfo/edu-sig
Re: [Edu-sig] Mystery Number 6174
"kirby urner" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]
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
funtopic.converge()
9822: 9822 - 2289 == 7533
7533: 7533 - 3357 == 4176
4176: 7641 - 1467 == 6174
funtopic.converge()
6685: 8665 - 5668 == 2997
2997: 9972 - 2799 == 7173
7173: 7731 - 1377 == 6354
6354: 6543 - 3456 == 3087
3087: 8730 - 0378 == 8352
8352: 8532 - 2358 == 6174
Here's one way to test the result. Think of a different way?
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])
def converge(closer = 6174):
ournum = somenum()
while True:
smallest = sorted(list(ournum))
highest = reversed(smallest)
strhi, strlo = "".join(highest), "".join(smallest)
diff = int(strhi) - int(strlo)
print( "%s: %s - %s == %s" % (ournum, strhi, strlo, diff) )
if diff == closer: return
ournum = str(diff)
Kirby
Related reading:
http://controlroom.blogspot.com/2007/01/aguirre-wrath-of-god-movie-review.html
The following tests all possible 4-digit combos, excluding "all 4 digits
*not* be the same one". It turns out seven iterations is the maximum it
takes to converge for any number.
def converge(n, maxiter=7):
i = 0 # iteration count
while n != 6174 and i < maxiter:
i += 1
L=list(str(n).zfill(4))
min_n = int(''.join(sorted(L)))
max_n = int(''.join(sorted(L, reverse=True)))
n = max_n - min_n
return n == 6174
for n in [i for i in xrange(1) if i % != 0]:
if not converge(n):
print 'FAILED'
break
else:
print 'PASSED'
___
Edu-sig mailing list
Edu-sig@python.org
http://mail.python.org/mailman/listinfo/edu-sig
Re: [Edu-sig] Mystery Number 6174
This is interesting trying 7 digits 000 reached by 10 inputs 8429652 reached by 990 inputs The probability of a single fixed point in in 10**7 numbers is quite small. On Jul 6, 2008, at 4:32 PM, Tim Peters wrote: trying 7 digits 000 reached by 10 inputs 8429652 reached by 990 inputs ___ Edu-sig mailing list Edu-sig@python.org http://mail.python.org/mailman/listinfo/edu-sig
Re: [Edu-sig] Mystery Number 6174
[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(1)
if n % :
return "%04d" % n
Note that all 4 digits are the same if and only if n is a multiple of .
> ...
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
reached by 10 inputs
6174 reached by 9990 inputs
trying 5 digits
0 reached by 10 inputs
53955 reached by 3190 inputs
63954 reached by 48480 inputs
74943 reached by 48320 inputs
trying 6 digits
00 reached by 10 inputs
549945 reached by 1950 inputs
631764 reached by 62520 inputs
851742 reached by 935520 inputs
trying 7 digits
000 reached by 10 inputs
8429652 reached by 990 inputs
___
Edu-sig mailing list
Edu-sig@python.org
http://mail.python.org/mailman/listinfo/edu-sig
Re: [Edu-sig] Mystery Number 6174
kirby urner wrote:
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.
...
Here's one way to test the result. Think of a different way?
def counts(limit=7, closer=6174):
counts = [0] * limit
exceptions = set()
for ournum in range(1):
start = quad = ''.join(sorted('%04d' % ournum))
if quad[0] == quad[3] or quad in exceptions:
continue
for distance in range(limit):
diff = int(''.join(reversed(quad))) - int(quad)
if diff == closer:
break
quad = ''.join(sorted('%04d' % diff))
else:
exceptions.add(start)
counts[distance] += 1
return counts, sorted(exceptions)
-Scott
___
Edu-sig mailing list
Edu-sig@python.org
http://mail.python.org/mailman/listinfo/edu-sig
[Edu-sig] Mystery Number 6174
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 >>> funtopic.converge() 9822: 9822 - 2289 == 7533 7533: 7533 - 3357 == 4176 4176: 7641 - 1467 == 6174 >>> funtopic.converge() 6685: 8665 - 5668 == 2997 2997: 9972 - 2799 == 7173 7173: 7731 - 1377 == 6354 6354: 6543 - 3456 == 3087 3087: 8730 - 0378 == 8352 8352: 8532 - 2358 == 6174 Here's one way to test the result. Think of a different way? 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]) def converge(closer = 6174): ournum = somenum() while True: smallest = sorted(list(ournum)) highest = reversed(smallest) strhi, strlo = "".join(highest), "".join(smallest) diff = int(strhi) - int(strlo) print( "%s: %s - %s == %s" % (ournum, strhi, strlo, diff) ) if diff == closer: return ournum = str(diff) Kirby Related reading: http://controlroom.blogspot.com/2007/01/aguirre-wrath-of-god-movie-review.html ___ Edu-sig mailing list Edu-sig@python.org http://mail.python.org/mailman/listinfo/edu-sig
