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 May 21, 2026

Problem #0207

Level Level 06

Solved By 5,308

Languages C++, Python

Answer 44043947822

Length 278 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

Mathematical Development

Substitution

Let $x = 2^t$ . Then $4^t = (2^t)^2 = x^2$ , so

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

For integer $x \geq 2$ , the admissible values of $k$ are therefore

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

Counting Partitions

At the boundary value $k = x(x-1)$ , the total number of partitions counted by $P(k)$ is exactly the number of integers $y \geq 2$ with $y(y-1) \leq x(x-1)$ , namely $x - 1$ .

Perfect Partitions

A partition is perfect precisely when $x$ is a power of 2. Thus the perfect values are generated by

x = 2, 4, 8, 16, \ldots

and at the boundary $k = x(x-1)$ the number of perfect partitions is

\lfloor \log_2 x \rfloor.

Ratio Analysis

Hence, for $k = x(x-1)$ ,

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

As $k$ moves between two consecutive admissible values, neither the numerator nor the denominator changes, so the minimum is attained at one of these boundary points.

Finding the Threshold

We need

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

which is equivalent to

x - 1 > 12345 \cdot \lfloor \log_2 x \rfloor.

For $\lfloor \log_2 x \rfloor = 17$ , we require

x - 1 > 12345 \cdot 17 = 209865,

so the first candidate is $x = 209867$ . This indeed satisfies $\lfloor \log_2 209867 \rfloor = 17$ , giving

k = 209867 \cdot 209866 = 44043947822.

Editorial

The substitution $x = 2^t$ completely linearizes the problem. Instead of reasoning about real exponents, we only need to study the integer sequence $k = x(x-1)$ . Up to the boundary value indexed by $x$ , there are exactly $x-1$ admissible partitions, and the perfect ones are exactly those with $x$ equal to a power of 2, so there are $\lfloor \log_2 x \rfloor$ of them.

That means the ratio $P(k)$ at a boundary point is just $\lfloor \log_2 x \rfloor / (x-1)$ . The answer is therefore the first $x$ for which $(x-1)$ overtakes $12345 \lfloor \log_2 x \rfloor$ , and then we convert back to $k = x(x-1)$ .

Pseudocode

target = 12345
x = 2

Repeat:
    perfect_count = floor(log_2(x))
    If x - 1 > target * perfect_count:
        return x * (x - 1)
    Increase x by 1

Complexity Analysis

Time: $O(x^\*)$ , where $x^\*$ is the first integer satisfying the threshold inequality.
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)