This problem was pretty interesting and I especially loved that the solution was so simple. There’s a real beauty to something that can be solved in so few lines of code. It really pleases me.
The solution relied just on a bit of algebra. Since we are looking for integer solutions, we can replace \(2^t\) with the variable \(r\).
\[4^t=2^t+k\] \[(2^2)^t=2^t+k\] \[(2^t)^2=2^t+k\] \[r^2=r+k\] \[k=r^2-r=r(r-1)\]Stepping through all integer values of $r$ will give us all possible solutions for $k$. This is the denominator in our ratio.
To find the perfect solutions, we need to find solutions where $t$ is also an integer. But since we already have integer solutions for $r=2^t$. Therefore, $t$ will be an integer when $r$ is a power of $2$. This is the numerator in our ratio.
def solve(n):
perfect, root, pow2 = 0, 1, 2
while True:
root += 1
if root == pow2:
perfect += 1
pow2 <<= 1
if perfect / (root - 1) < 1 / n:
return root * (root - 1)
if __name__ == '__main__':
import sys
n = eval(sys.argv[1])
print(solve(n))
import pytest
from problem import solve
_test_solve = (
(2, 30),
(3, 110),
(4, 182),
(5, 462),
(6, 650),
(7, 870),
(8, 1722),
(9, 2162),
(10, 2652),
(11, 3192),
(12, 3782),
(13, 6320),
(14, 7310),
(15, 8372),
(16, 9506),
(17, 10712),
(18, 11990),
(19, 13340),
(20, 14762),
(21, 22052),
(22, 24180),
(23, 26406),
(24, 28730),
(25, 31152),
(26, 33672),
(27, 36290),
(28, 39006),
(29, 41820),
(30, 44732),
(31, 47742),
(32, 50850),
)
@pytest.mark.parametrize('n,expect', _test_solve)
def test_solve(n, expect):
assert expect == solve(n)