p206.py 1.46 KB
 Nayuki committed Dec 26, 2016 1 2 ``````# # Solution to Project Euler problem 206 `````` Nayuki committed Dec 27, 2016 3 ``````# Copyright (c) Project Nayuki. All rights reserved. `````` Nayuki committed Dec 26, 2016 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 ``````# # https://www.nayuki.io/page/project-euler-solutions # https://github.com/nayuki/Project-Euler-solutions # # The major optimization is to do arithmetic in base 10 in the main loop, avoiding division and modulo def compute(): # Initialize n = 1000000000 # The pattern is greater than 10^18, so start searching at 10^9 ndigits = [0] * 10 # In base 10, little-endian temp = n for i in range(len(ndigits)): ndigits[i] = temp % 10 temp //= 10 n2digits = [0] * 19 # Based on length of pattern temp = n * n for i in range(len(n2digits)): n2digits[i] = temp % 10 temp //= 10 # Increment and search while not is_concealed_square(n2digits): # Add 20n + 100 so that n2digits = (n + 10)^2 add_20n(ndigits, n2digits) add_10pow(n2digits, 2) # Since n^2 ends with 0, n must end with 0 n += 10 add_10pow(ndigits, 1) # Now n2digits = n^2 return str(n) def is_concealed_square(n): for i in range(1, 10): # Scan for 1 to 9 if n[20 - i * 2] != i: return False return n[0] == 0 # Special case for 0 def add_10pow(n, i): while n[i] == 9: n[i] = 0 i += 1 n[i] += 1 def add_20n(n, n2): carry = 0 i = 0 while i < len(n): sum = n[i] * 2 + n2[i + 1] + carry n2[i + 1] = sum % 10 carry = sum // 10 i += 1 i += 1 while carry > 0: sum = n2[i] + carry n2[i] = sum % 10 carry = sum // 10 i += 1 if __name__ == "__main__": print(compute())``````