整数分拆方程

某些正整数k能写成$4^t=2^t+k$的分拆方程，其中t是实数，而$4^t$，$2^t$和k均为正整数。 前两个这样的分拆分别是$4^1=2^1+2$和$4^{1.5849625\ldots}=2^{1.5849625\ldots}+6$。 若t也是整数，则称这样的分拆是完美的。记 $$P(m)=\frac{|\{k=4^t-2^t: k\in\mathbb N, k\le m, t\in \mathbb N\}|}{|\{k=4^t-2^t: k\in\mathbb N, k\le m\}|}$$ 是不超过m的、能分拆的数中能作完美分拆的数的比例。 例如 $$P(6)=\frac{|\{2\}|}{|\{2,6\}|}=\frac{1}{2}.$$ 以下列出了$P(m)$的部分值： \begin{align*} P(5)&=1/1 \\ P(10)&=1/2 \\ P(15)&=2/3 \\ P(20)&=1/2 \\ P(25)&=1/2 \\ P(30)&=2/5 \\ \ldots P(180)&=1/4 \\ P(185)&=3/13 \\ \end{align*} 求能使$P(m)< 1/12345$的最小m。 注：原题对$P(m)$的定义不甚准确，此处对定义和例子都作了更精确的描述。

本题难度:

解答

一道故弄玄虚的题。 令$x=2^t$，则$k=x^2-x$。x可以取大于或等于2的自然数，且当其为2的幂时为完美分拆。 记$a_x=\lfloor\log_2x\rfloor$，即$2^{a_x}$是最大的、不超过$x$的$2$的幂。则对$(x+1)^2-(x+1)>m\ge x^2-x$都有 $$P(m)=\frac{a_x}{x-1},$$ 因此最小的满足条件的m必定也是$x^2-x$形式的数，且简单尝试即得此时$a_x=17$，从而有$17/(x-1)<1/12345$，即 $$x>12345*17+1=209866,$$ 因此$x=209867$，$m=209867^2-209867=44043947822$。 本题无需编程。