Skip to content

Instantly share code, notes, and snippets.

@Diapolo10
Created September 22, 2022 14:03
Show Gist options
  • Save Diapolo10/1686e45e637af7f644f006df9b6f6ca2 to your computer and use it in GitHub Desktop.
Save Diapolo10/1686e45e637af7f644f006df9b6f6ca2 to your computer and use it in GitHub Desktop.
[Python] Powers of 2
"""
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()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment