Project Euler 207

题目

Integer partition equations

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

The first two such partitions are $4^1 = 2^1 + 2$ and $4^{1.5849625\dots} = 2^{1.5849625\dots} + 6$.

Partitions where $t$ is also an integer are called perfect.

For any $m \ge 1$ let $P(m)$ be the proportion of such partitions that are perfect with $k \le m$.

Thus $P(6) = 1/2$.

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

$\begin{aligned}
P(5) &= &1/1 \
P(10)& = &1/2 \
P(15) &= &2/3 \
P(20) &= &1/2 \
P(25) &= &1/2 \
P(30) &= &2/5 \
&\dots&\
P(180) &=& 1/4\
P(185) &=& 3/13
\end{aligned}$

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

解决方案

令$x=2^t(x>0)$，那么上面的方程就可以化成$x^2-x=k$。

那么，当$x$为某一个正整数时，$x^2=x+k$就是一个划分，那么$k$就必须满足$k=x^2-x,x=1,2,\dots$。

回到题目中，如果$t$是一个整数，那么$x=2^t$就必须是一个二次幂。

这启发我们先从小到大遍历$x$值，然后再判断$x$值是否为一个二次方数，计算出完美划分比率，直接进行判断。

其中，使用如下代码判断一个有符号数$x$是否为一个二次方数：

(x & (x - 1)) == 0

最终，答案是一个形如$x^2-x$的整数。

代码

from itertools import count

Q = 12345
cnt = 0
for x in count(2, 1):
    if (x & (x - 1)) == 0:
        cnt += 1
    if cnt * Q < x - 1:
        ans = x * (x - 1)
        break
print(ans)