Dec 29th, 2012
26
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. """puzzle from Labyrint van Occam
2. """
3. def extend(number, length):
5.     f = 10 ** length
6.     f10 = 10 * f
7.     for digit in range(10):
8.         cand = f * digit + number
9.         if cand == pow(cand, 2, f10):
10.             return cand
11.
12. def make_long(number, N):
13.     """N: desired length of number"""
14.     for i in xrange(1, N):
15.         number = extend(number, i)
16.     return number
17.
18. def make_long5(N):
19.     """N: desired length of number
20.       simply square number and add digit i+1 to number (or
21.       calculate number**2 % 10**i+1)
22.    """
23.     number = 5
24.     p = 10
25.     for i in xrange(1, N):
26.         p *= 10
27.         number = (number * number) % p
28.     return number
29.
30. NEXT6 = dict(zip("3710926485",[int(s) for s in "7390184625"]))
31. def make_long6(N):
32.     """N: desired length of number
33.    """
34.     number = 6
35.     p = 1
36.     for i in xrange(1, N):
37.         p *= 10
38.         n = NEXT6[str(number * number)[-i-1]]
39.         number += n * p
40.     return number
41.
42.
43. N = 100
44.
45. N5 = make_long5(N)
46. N6 = 10 ** N + 1 - N5
47. print "{0:d}: {1:s}".format(5, str(N5).zfill(N))
48. print "{0:d}: {1:s}".format(6, str(N6).zfill(N))
RAW Paste Data