Project Euler

Integer Partition Equations

For the equation 4^t = 2^t + k, if we set x = 2^t, then k = x(x-1). For each integer x >= 2, this gives a distinct positive integer k and a corresponding real t = log_2 x. Each such (k, t) pair is...

Source sync Apr 19, 2026

Problem #0207

Level Level 06

Solved By 5,308

Languages C++, Python

Answer 44043947822

Length 259 words

geometryoptimizationsequence

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)$.

\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\\ \cdots &\\ P(180) &= 1/4\\ P(185) &= 3/13 \end {align*}

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

Problem 207: Integer Partition Equations

Analysis

Substitution

Let $x = 2^t$ . Then $4^t = (2^t)^2 = x^2$ and the equation becomes:

x^2 = x + k \implies k = x(x-1)

For integer $x \geq 2$ , we get the sequence of valid $k$ -values:

k = 2, 6, 12, 20, 30, 42, 56, 72, 90, 110, \ldots

Counting Partitions

The total number of partitions up to a given $k$ is the number of integers $x \geq 2$ such that $x(x-1) \leq k$ . At the boundary $k = x(x-1)$ , the total count is $x - 1$ .

Perfect Partitions

A partition is perfect when $x = 2^m$ for positive integer $m$ . The corresponding $k$ -values are:

$m=1$ : $x=2$ , $k=2$
$m=2$ : $x=4$ , $k=12$
$m=3$ : $x=8$ , $k=56$
$m=4$ : $x=16$ , $k=240$

The number of perfect partitions up to $k = x(x-1)$ is $\lfloor \log_2(x) \rfloor$ .

Ratio Analysis

At boundary points $k = x(x-1)$ :

P(k) = \frac{\lfloor \log_2(x) \rfloor}{x - 1}

Between boundary points, the total count stays constant while $k$ increases, but $P$ does not decrease (it can only increase if a perfect partition falls in the interval). Thus $P$ is minimized at the left endpoints $k = x(x-1)$ .

Finding the Threshold

We need the smallest $x$ such that:

\frac{\lfloor \log_2(x) \rfloor}{x - 1} < \frac{1}{12345}

Equivalently: $(x-1) > 12345 \cdot \lfloor \log_2(x) \rfloor$ .

For $x$ slightly above $2^{17} = 131072$ : $\lfloor \log_2(x) \rfloor = 17$ , and we need $x - 1 > 12345 \times 17 = 209865$ , so $x \geq 209867$ .

Checking: $x = 209867$ , $\lfloor \log_2(209867) \rfloor = 17$ (since $2^{17} = 131072 < 209867 < 262144 = 2^{18}$ ).

So $k = 209867 \times 209866 = 44043947822$ .

Correctness

Theorem. The method described above computes exactly the quantity requested in the problem statement.

Proof. The preceding analysis identifies the admissible objects and derives the formula, recurrence, or exhaustive search carried out by the algorithm. The computation evaluates exactly that specification, so every valid contribution is included once and no invalid contribution is counted. Therefore the returned value is the required answer. $\square$

Complexity

Time: $O(x^*) \approx O(2 \times 10^5)$ iterations.
Space: $O(1)$ .

Answer

\boxed{44043947822}

C++ project_euler/problem_207/solution.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    // 4^t = 2^t + k, let x = 2^t, then k = x(x-1).
    // Partitions are indexed by integer x >= 2.
    // Total partitions up to k = x(x-1): x - 1.
    // Perfect partitions: x is a power of 2.
    // Count of perfect partitions up to k = x(x-1): floor(log2(x)).
    // P(k) = floor(log2(x)) / (x-1).
    // P(k) is minimized at left endpoints k = x(x-1).
    // Find smallest x(x-1) where (x-1) > 12345 * floor(log2(x)).

    long long target = 12345;

    for (long long x = 2; x < 300000; x++) {
        int m = 63 - __builtin_clzll(x); // floor(log2(x))
        if ((x - 1) > target * m) {
            cout << x * (x - 1) << endl;
            return 0;
        }
    }

    return 0;
}

Python project_euler/problem_207/solution.py

"""
Problem 207: Integer Partition Equations

4^t = 2^t + k. Let x = 2^t, then k = x^2 - x = x(x-1).
For integer x >= 2, each x gives a distinct positive integer k, so k takes values
2, 6, 12, 20, 30, 42, 56, ... (these are the "partitions").

Total partitions up to k: the number of integers x >= 2 with x(x-1) <= k.
For k = x(x-1), this is x - 1.

Perfect partitions: those where t is a positive integer, i.e., x = 2^m for m >= 1.
Perfect k values: 2, 12, 56, 240, 992, ...

P(k) = (# perfect partitions up to k) / (# total partitions up to k).

At k = x(x-1): P = floor(log2(x)) / (x - 1).
P is minimized at the left endpoint of each interval [x(x-1), (x+1)x - 1].

We need the least k with P(k) < 1/12345, i.e., the smallest x(x-1) where
(x-1) > 12345 * floor(log2(x)).
"""

import math

def solve():
    target = 12345
    for x in range(2, 10**8):
        m = x.bit_length() - 1  # floor(log2(x))
        if (x - 1) > target * m:
            return x * (x - 1)
    return None

answer = solve()
assert answer == 44043947822
print(answer)