AI summary by TwinMind
Problems with Powers of Two - Numberphile
Numberphile
10m 56s
Problem Statement
- Pick four distinct integers (positive/negative) where pairwise sums are powers of 2
- Goal: maximize number of powers of 2 obtained from all possible pairs
- Example: 1,1,1,1 would give 6 powers of 2 (all pairs sum to 2) but numbers must be distinct
Solutions for Small Cases
- n=1: No solution (no pairs possible)
- n=2: Solution exists - take 1 and 3 (sum = 4 = 2²), gives 1 power of 2
- Alternative: 3 and 5 (sum = 8 = 2³)
- n=3: Best solution is -1, 3, 5
- -1+3 = 2, -1+5 = 4, 3+5 = 8
- Achieves maximum possible: 3 powers of 2 (3 choose 2 = 3)
- n=4: Best known solution is -3, -1, 3, 5
- -3+5 = 2, -1+3 = 2, -1+5 = 4, 3+5 = 8
- Gives 4 powers of 2 out of 6 possible pairs
- Status: Open question - unknown if 4 is optimal
Research Background
- Problem originated from Stan Wagon's Problem of the Week #1321
- Column running since 1968 from Macalester College, Saint Paul, Minnesota
- Stan Wagon took over in 1993, still running
- Original question: for n=10 numbers, how many powers of 2 possible?
Rob Pratt's Computational Approach
- Expert in MILP (Mixed Integer Linear Programming)
- Solved by restricting numbers to range [-n+3, n+3]
- For n=10: proved 15 is optimal within this range
- Various people found 14 solutions, couple found 15
- Limitation: Only works with bounded search range, not general solution
n=5 Case Analysis
- Best solution: -3, -1, 3, 5, 11
- Pairs yielding powers of 2:
- -3+5 = 2, -3+11 = 8, -1+3 = 2, -1+5 = 4, 5+11 = 16
- Total: 6 powers of 2 (includes repeated values 2 and 8)
- Rob Pratt's restricted range found -4, -3, -1, 3, 5 giving only 5 powers
- Status: a(5) = 6? (questionable)
General Observations
- Sequence extends to n=100 with plausible but doubtful answers
- For n=10: 15 out of 45 possible pairs (10 choose 2) achieved
- Performance degrades significantly as n increases
- Stan Wagon and Rob Pratt developed lower bounds showing moderate performance possible
- Problem appears computationally intractable for unrestricted integers
