Problem 207: Integer Partition Equations

Project Euler Problem 207 Solution

EulerSolve provides an optimized solution for Project Euler Problem 207, Integer Partition Equations, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary The equation $4^t = 2^t + k$ defines the partitions considered in this problem. If we set $m = 2^t$, then $4^t = m^2$, so every valid partition must satisfy $$m^2 = m + k,\qquad k = m(m-1).$$ Because the partition is required to be integral, $m = 2^t$ must itself be an integer. Conversely, every integer $m \ge 2$ gives one valid partition by taking $t = \log_2 m$. Thus the problem is really about the sequence $k_m = m(m-1)$ for $m=2,3,4,\dots$. A partition is called perfect when $t$ is an integer. In the new parameterization that means exactly that $m$ is a power of two. For a bound $K$, the quantity $P(K)$ is the proportion of partitions with $k \le K$ that are perfect. The goal is to find the smallest $K$ for which $P(K) < \frac{1}{12345}$. Mathematical Approach The key simplification is that the equation can be indexed by the integer $m=2^t$. Once that is done, the only special values are the powers of two, so the whole problem becomes a discrete counting argument. Reparameterizing the equation Start from $$4^t = 2^t + k.$$ With $m = 2^t$, we get $4^t = (2^t)^2 = m^2$, so $$m^2 = m + k,$$ and therefore $$k = m^2 - m = m(m-1).$$ This already explains why the implementations never work with real exponents directly. They only need the integer parameter $m$, because the exponent can always be recovered as $t = \log_2 m$....

Detailed mathematical approach

Problem Summary

For a positive integer $k$ we look for a real number $t$ with $4^t=2^t+k$ in which $4^t$ and $2^t$ are positive integers as well; the problem calls such an equation an integer partition, or simply a partition. The first two are $4^1=2^1+2$ and $4^{1.5849625\cdots}=2^{1.5849625\cdots}+6$. A partition is perfect if $t$ is also an integer. For $m\ge1$, $P(m)$ is the proportion of perfect partitions among the partitions with $k\le m$; thus $P(6)=1/2$, and the statement lists $P(5)=1/1$, $P(10)=1/2$, $P(15)=2/3$, $P(20)=1/2$, $P(25)=1/2$, $P(30)=2/5$, $P(180)=1/4$ and $P(185)=3/13$. We must find the smallest $m$ for which $P(m)\lt1/12345$. ^[1]

The whole solution in one sentence: writing $n=2^t$, the partitions in increasing order are $k=n(n-1)$ for $n=2,3,4,\dots$, and the perfect ones are those in which $n$ is a power of two, so we go through these $n$, count the powers of two along the way, and stop at the first $n$ at which fewer than one in $12345$ of the partitions so far are perfect; that partition's $k=n(n-1)$ is the requested $m$.

Mathematical Approach

We first turn the equation with a real exponent into a statement about whole numbers, then count the partitions up to a bound, and finally find where the proportion first drops below the threshold. We write the threshold as $1/d$ with $d=12345$; every argument works for any positive integer $d$, which lets us test it on small thresholds.

1. Small cases

Put $n=2^t$. Then $4^t=(2^2)^t=(2^t)^2=n^2$, so the equation becomes $n^2=n+k$, that is,

$$k=n^2-n=n(n-1).$$

Trying the first whole numbers $n$:

$n=2$: $t=1$ and $k=2$, the first partition of the statement; it is perfect;
$n=3$: $t=\log_2 3=1.5849625\ldots$ and $k=6$, the second one;
$n=4$: $t=2$ and $k=12$, perfect;
$n=5,6,7$: $t=2.3219\ldots$, $2.5849\ldots$, $2.8073\ldots$ and $k=20,30,42$;
$n=8$: $t=3$ and $k=56$, perfect.

The value $n=1$ would give $t=0$ and $k=0$, which is not positive, so it does not count.

2. Every partition comes from a whole number

Claim. The partitions correspond one to one to the integers $n\ge2$: the partition of $n$ has $t=\log_2 n$ and $k=n(n-1)$, and different $n$ give different $k$.

Proof. In a partition, $n=2^t$ is a positive integer by the rules of the problem, and Section 1 gives $k=n(n-1)$; since $k\ge1$, $n$ cannot be $1$, so $n\ge2$. Conversely, for an integer $n\ge2$ the real number $t=\log_2 n$ gives $2^t=n$ and $4^t=n^2$, both positive integers, and $k=n(n-1)\ge2$ is a positive integer, so $4^t=2^t+k$ is a partition. Finally,

$$(n+1)n-n(n-1)=2n\gt0,$$

so $k$ strictly increases with $n$. $\square$

So a given $k$ has at most one partition, and it has one exactly when $k$ is a product of two consecutive integers: $2,6,12,20,30,42,56,\dots$, the oblong numbers. ^[2] For instance $k=7$ has none, because the positive solution of $x^2=x+7$ is $x=(1+\sqrt{29})/2\approx3.19$, not an integer.

3. Perfect partitions

The exponent $t=\log_2 n$ is an integer exactly when $n$ is a power of two, $n=2^t$ with $t\ge1$. The perfect partitions therefore belong to $n=2,4,8,16,32,\dots$ and have

$$k=4^t-2^t=2,\ 12,\ 56,\ 240,\ 992,\ \dots,$$

the sequence $4^t-2^t$ of the OEIS. ^[3] For every other $n$, $t$ is not even a fraction: if $\log_2 n=a/b$ with positive integers $a$ and $b$, then $n^b=2^a$, so $2$ is the only prime factor of $n$ and $n$ is a power of two after all. That is why the statement writes $1.5849625\cdots$ with dots: $\log_2 3$ is irrational, the classic case of this argument, since $2^a$ is even and $3^b$ is odd. ^[4]

4. Counting the partitions up to a bound

For $m=1$ no partition has $k\le1$, so the proportion is defined from $m=2$ on. Fix $m\ge2$ and let $N=N(m)$ be the largest integer $n$ with $n(n-1)\le m$. By Section 2, the partitions with $k\le m$ are those of $n=2,3,\dots,N$, so there are $N-1$ of them. The perfect ones belong to the powers of two $2^1,2^2,\dots,2^p$ up to $N$, where $2^p\le N\lt2^{p+1}$; hence their number is $p=\lfloor\log_2 N\rfloor$, where $\lfloor x\rfloor$ denotes the largest integer not exceeding $x$; this is one less than the number of binary digits of $N$. ^[5] Therefore

$$P(m)=\frac{\lfloor\log_2 N\rfloor}{N-1},\qquad N=N(m).$$

The bound $N(m)$ has a closed form: multiplying $n(n-1)\le m$ by $4$ and adding $1$ gives $(2n-1)^2\le4m+1$, so

$$N(m)=\left\lfloor\frac{1+\sqrt{4m+1}}{2}\right\rfloor.$$

5. Worked example: the table of the statement

$m=5$: $N=2$, because $2\cdot1=2\le5\lt6=3\cdot2$; there is one partition, and it is perfect, so $P(5)=1/1$.
$m=6$ and $m=10$: $N=3$; of the partitions $k=2$ and $k=6$ one is perfect, so the proportion is $1/2$.
$m=15$: $N=4$, since $12\le15\lt20$; two of three are perfect, so $P(15)=2/3$.
$m=20$ and $m=25$: $N=5$, so the proportion is $2/4=1/2$; $m=30$: $N=6$, so $P(30)=2/5$.
$m=180$: $N=13$, since $13\cdot12=156\le180\lt182=14\cdot13$; the perfect partitions are those of $n=2,4,8$, so $P(180)=3/12=1/4$.
$m=185$: $N=14$, so $P(185)=3/13$.

All nine values agree with the statement.

6. A step function that jumps upwards

$P(m)$ changes only when $m$ reaches the next value $k=n(n-1)$, and then $N$ grows by one. If the new $n$ is not a power of two, only the denominator grows and $P$ falls. If $n=2^q$ with $q\ge2$, numerator and denominator both grow by one, and $P$ rises, because

$$\frac{q}{2^q-1}\gt\frac{q-1}{2^q-2}\iff2^q\gt q+1.$$

For example $P(11)=1/2$ but $P(12)=2/3$, and $P(55)=1/3$ but $P(56)=3/7$; the table of the statement shows the same rise from $P(10)$ to $P(15)$. So $P$ is not monotone, and once it is below a threshold it may climb back above it, as Section 8 shows. We therefore really need the first $m$, and a bisection on $m$ is not safe: searching $2\le m\le600$ for the first $m$ with $P(m)\lt1/4$, it tests $m=301$ first, finds $P(301)=1/4$, moves to the right and ends at $m=306$ instead of the correct $182$.

7. The first crossing

Both denominators in $P(m)\lt1/d$ are positive, so multiplying out gives an inequality between integers:

$$P(m)\lt\frac1d\iff d\,\lfloor\log_2 N\rfloor\lt N-1.$$

Claim. Let $n_d$ be the smallest integer $n\ge2$ with $d\lfloor\log_2 n\rfloor\lt n-1$. The smallest $m$ with $P(m)\lt1/d$ is $m=n_d(n_d-1)$.

Proof. If $2\le m\lt n_d(n_d-1)$, then $2\le N(m)\lt n_d$, so $N(m)$ fails the inequality by the choice of $n_d$, and $P(m)\ge1/d$. For $m=n_d(n_d-1)$ we have $N(m)=n_d$, which satisfies it. $\square$

The proof uses only that $k$ increases with $n$, so a scan over $n=2,3,4,\dots$ is correct even though $P$ is not monotone. Section 8 shows that $n_d$ exists.

8. Solving block by block

Group the integers $n$ into blocks $2^p\le n\lt2^{p+1}$, on which $\lfloor\log_2 n\rfloor=p$. Inside block $p$ the inequality reads $n\ge pd+2$, so the block contains a solution exactly when $pd+2\le2^{p+1}-1$. Let $p_d$ be the smallest $p\ge1$ with

$$pd+3\le2^{p+1};$$

it exists, since $2^{p+1}$ grows faster than any linear function of $p$.

Claim. $n_d=p_d\,d+2$.

Proof. Blocks with $p\lt p_d$ contain no solution, and in block $p_d$ the smallest solution is the larger of $2^{p_d}$ and $p_d d+2$. If $p_d=1$, then $d+3\le4$, so $d=1$ and the larger number is $3=d+2$. If $p_d\ge2$, block $p_d-1$ has no solution, so $(p_d-1)d+3\gt2^{p_d}$, that is, $2^{p_d}\le(p_d-1)d+2\lt p_d d+2$. $\square$

For $d=4$, the numbers $pd+3$ are $7$, $11$, $15$ for $p=1,2,3$, against $2^{p+1}=4$, $8$, $16$; so $p_4=3$, $n_4=14$, and the smallest $m$ with $P(m)\lt1/4$ is $14\cdot13=182$. This fits the table of the statement: $P(181)=3/12=1/4$, and $P(182)=3/13$ is the value listed for $m=185$. At $n=16$ the proportion climbs back to $P(240)=4/15\gt1/4$, and it falls below $1/4$ again only at $m=18\cdot17=306$, where $P(306)=4/17$. The published C++ program checks two other thresholds: $d=3$ gives $p_3=3$, $n_3=11$ and $m=110$, with $P(110)=3/10$; $d=10$ gives $p_{10}=5$, $n_{10}=52$ and $m=2652$, with $P(2652)=5/51$.

9. Why the inequality must be strict

In all three examples the proportion just before the answer is exactly $1/d$: $P(109)=3/9$, $P(181)=3/12$ and $P(2651)=5/50$. This holds for every $d\ge2$. Then $p_d\ge2$, and $n=p_d d+1$ still lies in block $p_d$, because $2^{p_d}\le(p_d-1)d+2\le p_d d+1$, so its proportion is $p_d/(p_d d)=1/d$. Testing $\le$ instead of $\lt$ answers a different question, the first $m$ with $P(m)\le1/d$, and it can stop much earlier: for $d=3$ it stops at $n=7$, that is $m=42$, where $P(42)=2/6=1/3$.

How the Code Works

In all three programs the loop variable m is the number $n=2^t$ of Section 2, not the bound $m$ of the statement; the requested bound is the product m * (m - 1), which the C++ function solve returns to main for printing, while the Python and Java versions print it directly inside the loop. The C++ program ^[7] keeps its settings in Options: denominator, the $d$ of the threshold, is $12345$ unless --denominator= gives other decimal digits, which parse_u64_after_prefix reads, and --skip-checkpoints switches the self-check off. parse_arguments rejects any other argument and the denominator $0$, and main then returns exit code $1$. Unless switched off, run_checkpoints requires solve(3) to return $110$ and solve(10) to return $2652$, the values of Section 8, and main returns exit code $2$ if one of them fails; otherwise it prints solve(options.denominator).

solve starts with p = 1, for the perfect partition of $n=2$, and next_pow2 = 4, and runs m through $2,3,4,\dots$. When m equals next_pow2, it increases p and doubles next_pow2 with a left shift. After this update p equals $\lfloor\log_2 n\rfloor$, the number of perfect partitions so far, and next_pow2 is the smallest power of two above $n$, as long as that power fits into 64 bits: both facts hold for $n=2$ and carry over from each $n$ to $n+1$, because $\lfloor\log_2 n\rfloor$ grows exactly at the powers of two. The test p * denominator < m - 1 is the inequality of Section 7, and the first success returns m * (m - 1), the smallest $m$ by the claim of that section. The program uses no logarithm and no floating-point number, which is safer: a double has a 53-bit significand, and doubles between $32$ and $64$ are $2^{-47}\approx7.1\cdot10^{-15}$ apart, so $\log_2(2^{49}-1)\approx49-2.6\cdot10^{-15}$ is rounded to exactly $49$, and a floating-point floor gives $49$ instead of $48$. ^[6]

Python's solve and Java's main run the same loop with the denominator fixed at $12345$, without options or checkpoints; Python takes m from range(2, 10**8), a limit far above what this denominator needs, and Java loops without a limit. For $d=12345$ every number involved fits easily into 64 bits, so the std::uint64_t of C++, the long of Java and the unbounded integers of Python give the same result. The C++ program also forms the product in its test as an unsigned __int128, ^[8] so that this multiplication cannot overflow, but its other 64-bit arithmetic is unchecked and works modulo $2^{64}$: ^[9] parse_u64_after_prefix reads, for example, the digits of $2^{64}+1$ as the denominator $1$, and the returned m * (m - 1) first overflows at the denominator $138\,547\,333$. For every smaller denominator the result is exact.

Complexity and Verification

Counting each operation on 64-bit numbers as one step, the loop runs $n_d-1$ times with constant work per step and keeps three changing integers, so the time is $O(n_d)$ and the memory is $O(1)$. By Section 8, $n_d=p_d d+2$, and $p_d$ grows like $\log d$. On the one hand $2^{p_d+1}\ge p_d d+3\gt d$, so $p_d\gt\log_2 d-1$. On the other hand, for $d\ge2$ let $r=\lceil\log_2 d\rceil$ be the smallest integer with $d\le2^r$; then $r\ge1$ and $r\le2^r-1$, so

$$2rd+3\le2(2^r-1)\,2^r+3\le2^{2r+1},$$

which shows that $p=2r$ satisfies the condition of Section 8, and hence $p_d\le2r$. The length $n_d$ of the scan therefore grows like $d\log d$; for example $n_{100}=902$ and $n_{1000}=13002$. For $d=12345$ fewer than a million iterations suffice, and each of the three programs ran in at most a few hundredths of a second. Section 8 would even give the answer in $O(\log d)$ steps, by trying $p=1,2,3,\dots$ until $pd+3\le2^{p+1}$; the published programs use the direct scan, which needs only Section 7.

Besides the C++ checkpoints for $d=3$ and $d=10$, the following checks were run for this article; they are not part of the published solutions.

A brute force that decides for every $k\le2\cdot10^6$, from the definition, whether $x^2=x+k$ has a positive integer solution $x=2^t$ confirmed the counts $N-1$ and $\lfloor\log_2 N\rfloor$ of Section 4 for every $m\le2\cdot10^6$, and with them every value of the statement's table.
The same pass found the first $m$ with $P(m)\lt1/d$ for every $d\le141$; all of them agree with $n_d(n_d-1)$ from Section 8.
The C++ program with --denominator=d agrees with Section 8 for every $d\le3000$, and the C++, Python and Java programs print the same number for $d=12345$, which also equals the value given by Section 8.
The claims of Sections 6 and 9 hold in all tested cases: $P$ rises exactly at the powers of two for all $n\lt2^{16}$, and the proportion just before the answer equals $1/d$ for every $2\le d\le10^5$.

Footnotes and References

The references below supply the background facts used above; the reduction to whole numbers, the counting formula, the block-by-block solution and the checks are derived in this article.

Project Euler 207 — Integer Partition Equations. The official statement: a partition is an equation 4^t = 2^t + k in which 4^t, 2^t and k are positive integers and t is a real number; the first two have k = 2 and k = 6; partitions with an integer t are perfect; P(m) is the proportion of perfect partitions among those with k ≤ m, with P(6) = 1/2 and a table of further values, and the task asks for the smallest m with P(m) < 1/12345.
OEIS A002378 — Oblong numbers. The oblong (or pronic) numbers a(n) = n(n + 1) are 0, 2, 6, 12, 20, 30, 42, 56, …; the entry also notes a(n − 1) = n² − n and a(n) = a(n − 1) + 2n, the values k and their gaps in Section 2.
OEIS A020522 — a(n) = 4^n − 2^n. The sequence 0, 2, 12, 56, 240, 992, 4032, … lists, from its second term on, the values k of the perfect partitions for t = 1, 2, 3, … (Section 3).
Wikipedia — Irrational number. Its section on logarithms proves that log₂ 3 is irrational: log₂ 3 = m/n would give 2^m = 3^n, an even number equal to an odd one.
Wikipedia — Binary logarithm. A positive integer n has ⌊log₂ n⌋ + 1 binary digits, and the integer binary logarithm ⌊log₂ n⌋ is the zero-based position of the most significant 1 bit of n.
Wikipedia — Double-precision floating-point format. A double has a 53-bit significand, 52 bits stored and one implicit, and in the range from 2^e to 2^(e+1) the representable numbers are spaced 2^(e − 52) apart; between 32 and 64 the spacing is therefore 2^(−47).
C++ — Euler207.cpp. The linked immutable C++ revision contains parse_arguments, solve and run_checkpoints. It is the implementation record for this article.
GCC manual — 128-bit Integers. GCC supports __int128 and unsigned __int128 on targets with an integer mode wide enough to hold 128 bits; the C++ program uses unsigned __int128 for the product in its test.
cppreference — Arithmetic operators. Unsigned integer arithmetic is performed modulo 2^N, where N is the number of bits of the type, so a 64-bit unsigned product that is too large wraps around instead of failing.

Problem 207 source code

C++

#include <cstdint>
#include <iostream>
#include <string>

namespace {

using u64 = std::uint64_t;
using u128 = unsigned __int128;

struct Options {
    u64 denominator = 12345ULL;
    bool run_checkpoints = true;
};

bool parse_u64_after_prefix(const std::string& arg, const std::string& prefix, u64& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }

    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    u64 parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10ULL + static_cast<u64>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);

        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_u64_after_prefix(arg, "--denominator=", options.denominator)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }

    return options.denominator >= 1ULL;
}

u64 solve(const u64 denominator) {
    u64 p = 1;
    u64 next_pow2 = 4;

    for (u64 m = 2;; ++m) {
        if (m == next_pow2) {
            ++p;
            next_pow2 <<= 1;
        }

        if (static_cast<u128>(p) * static_cast<u128>(denominator) < static_cast<u128>(m - 1)) {
            return m * (m - 1);
        }
    }
}

bool run_checkpoints() {
    if (solve(3ULL) != 110ULL) {
        std::cerr << "Checkpoint failed for threshold 1/3" << '\n';
        return false;
    }
    if (solve(10ULL) != 2652ULL) {
        std::cerr << "Checkpoint failed for threshold 1/10" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << solve(options.denominator) << '\n';
    return 0;
}

Python

# Problem 207: Integer partition equations
# 4^t = 2^t + k => m(m-1) = k where m = 2^t
# "perfect" if t is integer (m is power of 2)
# Find least k such that P(k)/count < 1/12345

def solve():
    denominator = 12345
    p = 1  # number of perfect partitions
    next_pow2 = 4
    for m in range(2, 10**8):
        if m == next_pow2:
            p += 1
            next_pow2 <<= 1
        # p * denominator < (m - 1)
        if p * denominator < (m - 1):
            print(m * (m - 1))
            return

solve()

Java

public class Euler207 {
    public static void main(String[] args) {
        long denominator = 12345;
        long p = 1, nextPow2 = 4;
        for (long m = 2;; m++) {
            if (m == nextPow2) {
                p++;
                nextPow2 <<= 1;
            }
            if (p * denominator < (m - 1)) {
                System.out.println(m * (m - 1));
                return;
            }
        }
    }
}