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\cdots} = 2^{1.5849625\cdots} + 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)$.
P(5) &= 1/1\\
P(10) &= 1/2\\
P(15) &= 2/3\\
P(20) &= 1/2\\
P(25) &= 1/2\\
P(30) &= 2/5\\
\cdots &\\
P(180) &= 1/4\\
P(185) &= 3/13

Find the smallest $m$ for which $P(m) \lt 1/12345$.

To solve this problem, we will start off by rewriting the provided question in more familiar terms.

The given integer partition of the form \[4^t = 2^t + k,\] can be simplified by dividing every term by \(2^t\) which gives us a new equation \[2^t = 1 + k/2^t.\]

The left hand side is the function \(2^t\) shown as a Cartesian graph. The right hand side can be seen as a hyperbolic graph of \(1 + k/x\).

Suppose we have a Cartesian graph of those two functions. A perfect partition is a situation when those two graphs intersect at an integer point x.

An answer to the problem would be the smallest hyperbola that doesn’t intersect the function \(2^t\) at any integer point \(x\).

By using a graphing tool or plotting a graph manually, or even inferring from the given proportions, we can observe that the rate of growth of the exponential function exceeds the rate of the hyperbola’s descending. Consequently, as \(m\) (which is our max \(k\)) increases, hyperbolas would start missing integer points on the \(2^t\) graph. Judging from the fact we are looking for proportion smaller than 1/12345, \(m\) must be large.

The accurate answer can be calculated only through an iterative process comparing the values of the two functions for each natural \(t\) until we reach a large enough \(m\) value that fails to intersect at any given integer. This computational problem is beyond the reach of human computation and requires the use of a computer to obtain the exact smallest \(m\).

More Answers:
Generalised Hamming Numbers
Dice Game
Concealed Square

Error 403 The request cannot be completed because you have exceeded your quota. : quotaExceeded


Recent Posts

Don't Miss Out! Sign Up Now!

Sign up now to get started for free!