Project Euler Problem 207

# Statement

For some positive integers k, there exists an integer partition of the form 4t = 2t + k,
where 4t, 2t, and k are all positive integers and t is a real number.

The first two such partitions are 41 = 21 + 2 and 41.5849625… = 21.5849625… + 6.

Partitions where t is also an integer are called perfect.
For any m 1 let P(m) be the proportion of such partitions that are perfect with p $\leq$ m.
Thus P(6) = 1/2.

In the following table are listed some values of P(m)

P(5) = 1/1
P(10) = 1/2
P(15) = 2/3
P(20) = 1/2
P(25) = 1/2
P(30) = 2/5

P(180) = 1/4
P(185) = 3/13

Find the smallest m for which P(m) 1/12345

# Solution

Let's start to process the equation:

(1)
\begin{array} {rcl} 4^{t} & = & 2^{t} + k \\ 2^{2t} & = & 2^{t} + k \\ 2^{2t} - 2^{t} & = & k \\ 2^{t} (2^{t} - 1) & = & k \\ \end{array}

It is easy to notice that for whatever 2t(which has to be integer) there will exist a corresponding k that will be integer. And like $4^{t} = {2^{t}}^{2}}$ then 4t will be integer. As t can be real we will have a valid solution to the equation for every t that 2t is integer. And the solution is perfect when t is integer too.

It is also important to notice that the function that defines k is increasing so for every t1 < t2 => k1 < k2.

Knowing that, it is easy to program an increasing function that counts the proportion of perfect partitions until the value we are looking for is reached.

from fractions import Fraction
from math import log

calc_k = lambda x: x * (x - 1)

cant_perf = 1
cant_tot = 1
limit = Fraction(1, 12345)

if __name__ == '__main__':
i = 3
while Fraction(cant_perf, cant_tot) >= limit:
log_2 = int(log(i,2))
if 2 ** log_2 == i:
cant_perf += 1
cant_tot += 1
i += 1
i -= 1
print("The result is:", calc_k(i))