pattern = '1_2_3_4_5_6_7_8_9_0'
Let's write a function that says if a given number is compatible with the pattern.
def is_compatible(number, pattern, start_from_end=True, joker='_'):
"""Checks whether number is compatible with pattern.
Can start the check at the beginning or the end of the number."""
number = int(number)
if start_from_end:
number_str = str(number)[::-1]
pattern = pattern[::-1]
else:
number_str = str(number)
until = min(len(number_str), len(pattern))
for a, b in zip(number_str, pattern):
if b == joker:
continue
if a != b:
return False
return True
is_compatible(123, '1_3')
True
is_compatible(123, '12_')
True
is_compatible(123, '12_', start_from_end=False)
True
from itertools import product
list(product([0, 3, 7], [0]))
[(0, 0), (3, 0), (7, 0)]
def build_numbers(*last_possible_digits):
if len(last_possible_digits) == 1 and len(last_possible_digits[0]) == 0:
yield 0
else:
for tup in product(*last_possible_digits):
yield int(sum(d * 10**(len(tup) -1 - i) for i, d in enumerate(tup)))
for n in build_numbers([0, 3, 7], [0]):
print(n)
0 30 70
for n in build_numbers([1, 2], [0, 3, 7], [0]):
print(n)
100 130 170 200 230 270
for n in build_numbers([]):
print(n)
0
possible_digits = set()
for digit in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]:
n = digit
if is_compatible(n**2, pattern, start_from_end=True):
possible_digits.add(digit)
list(possible_digits)
[0]
possible_digits = set()
for digit in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]:
for remainder in build_numbers([0]):
n = 10 * digit + remainder
if is_compatible(n**2, pattern, start_from_end=True):
possible_digits.add(digit)
list(possible_digits)
[0, 3, 7]
possible_digits = set()
for digit in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]:
for remainder in build_numbers([0, 3, 7], [0]):
n = 100 * digit + remainder
if is_compatible(n**2, pattern, start_from_end=True):
possible_digits.add(digit)
list(possible_digits)
[0, 8, 4, 5]
possible_digits = set()
for digit in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]:
for remainder in build_numbers([0, 8, 4, 5], [0, 3, 7], [0]):
n = 1000 * digit + remainder
if is_compatible(n**2, pattern, start_from_end=True):
possible_digits.add(digit)
list(possible_digits)
[0]
possible_digits = set()
for digit in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]:
for remainder in build_numbers([0], [0, 8, 4, 5], [0, 3, 7], [0]):
n = 10000 * digit + remainder
if is_compatible(n**2, pattern, start_from_end=True):
possible_digits.add(digit)
list(possible_digits)
[0, 4]
possible_digits = set()
for digit in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]:
for remainder in build_numbers([0, 4], [0], [0, 8, 4, 5], [0, 3, 7], [0]):
n = int(100000 * digit + remainder)
if is_compatible(n**2, pattern, start_from_end=True):
possible_digits.add(digit)
list(possible_digits)
[0]
possible_digits = set()
for digit in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]:
for remainder in build_numbers([0], [0, 4], [0], [0, 8, 4, 5], [0, 3, 7], [0]):
n = int(1000000 * digit + remainder)
if is_compatible(n**2, pattern, start_from_end=True):
possible_digits.add(digit)
list(possible_digits)
[0]
possible_digits = set()
for digit in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]:
for remainder in build_numbers([0], [0], [0, 4], [0], [0, 8, 4, 5], [0, 3, 7], [0]):
n = int(10000000 * digit + remainder)
if is_compatible(n**2, pattern, start_from_end=True):
possible_digits.add(digit)
list(possible_digits)
[0]
possible_digits = set()
for digit in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]:
for remainder in build_numbers([0], [0], [0], [0, 4], [0], [0, 8, 4, 5], [0, 3, 7], [0]):
n = int(100000000 * digit + remainder)
if is_compatible(n**2, pattern, start_from_end=True):
possible_digits.add(digit)
list(possible_digits)
[0]
Since the first digit is a 1, we can finish this.
for n in build_numbers([0, 1], [0], [0], [0, 4], [0], [0, 8, 4, 5], [0, 3, 7], [0]):
if is_compatible(n**2, pattern, start_from_end=False):
print(n)
n = 40830
n**2
1667088900
pattern
'1_2_3_4_5_6_7_8_9_0'
is_compatible(n**2, pattern, start_from_end=True)
True
end_digits = []
for current_power in range(12):
possible_digits = set()
for digit in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]:
for remainder in build_numbers(*end_digits):
n = digit * 10**current_power + remainder
if is_compatible(n**2, pattern, start_from_end=True):
possible_digits.add(digit)
print(n)
print(current_power, list(possible_digits))
end_digits.insert(0, list(possible_digits))
0 0 [0] 0 30 70 1 [0, 3, 7] 0 30 70 430 530 830 2 [0, 8, 4, 5] 0 30 70 830 430 530 3 [0] 0 30 70 830 430 530 40830 4 [0, 4] 0 30 70 830 430 530 40830 5 [0] 0 30 70 830 430 530 40830 6 [0] 0 30 70 830 430 530 40830 7 [0] 0 30 70 830 430 530 40830 8 [0] 0 30 70 830 430 530 40830 9 [0] 0 30 70 830 430 530 40830 10 [0] 0 30 70 830 430 530 40830 11 [0]
len(str(n**2))
24
len(pattern)
19
end_digits
[[0], [0], [0], [0], [0], [0, 4], [0], [0, 8, 4, 5], [0, 3, 7], [0]]
3 * 10**9
3000000000
list(build_numbers([]))
[]
build_numbers([])
<generator object build_numbers at 0x0000000008654200>
from math import sqrt
maxi = int(sqrt(int(pattern.replace('_', '9'))))
maxi
1389026623
mini = int(sqrt(int(pattern.replace('_', '0'))))
mini
1010101010
"40830"
'40830'
for i in range(1000000, 138999):
n = int(str(i) + str(830))
if is_compatible(n**2, pattern, start_from_end=False):
print(n)
is_compatible(n**2, pattern, start_from_end=False)
False
n
1389040830
n**2
1929434427407088900
pattern
'1_2_3_4_5_6_7_8_9_0'
len(str(n**2))
19
len(pattern)
19
is_compatible(7088900, pattern, start_from_end=True)
True
830**2
688900