[Python] Powers of 2

powers_of_2.py

"""
Experimenting with the Powers of 2 problem

https://www.youtube.com/watch?v=IPoh5C9CcI8
"""

import itertools
from math import log2

def is_power_of_2(num: int) -> bool:
    return log2(num).is_integer()

def power_sums(num: int, low_limit: int = -10, high_limit: int = 10) -> list[int]:
    max_powers = []
    theoretical_max = num * (num-1) // 2  # 0, 1, 3, 6, ...
    
    for powers in itertools.product((2**n for n in range(low_limit, high_limit+1)) for _ in range(num)):
        valid = []
        for pair in itertools.combinations(powers, 2):
            total = sum(pair)
            if total and is_power_of_2(total):
                valid.append(total)
        if len(valid) > len(max_powers):
            max_powers = valid
        if len(valid) == theoretical_max:
            break
    return max_powers, theoretical_max

def main():
    for num in range(1000):
        result, highest = power_sums(num+1)
        print(f"Num #{num+1}: {result}, {'non-' if len(result) < highest else ''}optimal")

if __name__ == '__main__':
    main()