deduce-pair-from-sum-and-product.py

# Solution to this puzzle: 
# https://www.cantorsparadise.com/can-you-design-an-algorithm-to-solve-this-lovely-logic-puzzle-bc674be1ffbf
# This algorithm does not use Goldbach's conjecture (this would cut the running time in half at least!)
list0 = []
for i in range(2,2022):
    for j in range(i+1,2023):
        list0.append([i,j])
print("Number of possible pairs initially: "+str(len(list0)))

# Statement 1
# create set of all pairs' products
# for any pair whose sum is unique in the product set, exclude this sum
products = set()
multiple_products = set()
for pair in list0:
    new_product = pair[0]*pair[1]
    if new_product in multiple_products:
        continue
    elif new_product in products:
        multiple_products.add(new_product)
    else:
        products.add(new_product)

unique_products = products.difference(multiple_products)

list1 = []
excluded_sums = set()
for pair in list0:
    if pair[0]*pair[1] in unique_products:
        excluded_sums.add(pair[0]+pair[1])

for pair in list0:
    if pair[0]+pair[1] not in excluded_sums:
        list1.append(pair)

print("Number of possible pairs after Harry's first statement: "+str(len(list1)))

# Statement 2
# only keep pairs whose product is unique
list2 = []
products = set()
multiple_products = set()    
for pair in list1:
    new_product = pair[0]*pair[1]
    if new_product in products:
        multiple_products.add(new_product)
    else:
        products.add(new_product)

for pair in list1:
    new_product = pair[0]*pair[1]
    if new_product not in multiple_products:
        list2.append(pair)

print("Number of possible pairs after Draco's statement: "+str(len(list2)))

# Statement 3
# only keep pairs whose sum is unique
list3 = []
sums = set()
multiple_sums = set()
for pair in list2:
    new_sum = pair[0] + pair[1]
    if new_sum in sums and new_sum not in multiple_sums:
        multiple_sums.add(new_sum)
    else:
        sums.add(new_sum)

for pair in list2:
    new_sum = pair[0] + pair[1]
    if new_sum not in multiple_sums:
        list3.append(pair)

print("Number of possible pairs after Harry's second statement: "+str(len(list3)))
print(list3)