Problem 247: Squares Under a Hyperbola

Project Euler Problem 247 Solution

EulerSolve provides an optimized solution for Project Euler Problem 247, Squares Under a Hyperbola, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary Problem 247 builds an infinite family of axis-aligned squares inside the region below the rectangular hyperbola $y=1/x$, starting from the corner $(1,0)$. From any exposed lower-left corner $(x,y)$, the next square is defined to be the unique largest square anchored at that corner whose upper-right corner still lies on the curve. Each square receives a label $(\text{left},\text{below})$. Moving to the right child increases $\text{left}$ by 1, and moving to the upper child increases $\text{below}$ by 1. All squares are then ranked globally by decreasing side length, not by tree depth. The actual target in this problem is the last square labeled $(3,3)$, so the task is to determine where the 20th such square appears in that global size order. Mathematical Approach The geometry gives a closed formula for the next square, and the recursive construction turns naturally into a best-first search on exposed corners. The crucial point is that the code never tries to list squares in depth-first or breadth-first order; it always extracts the currently largest available square. The maximal square anchored at a corner Fix a corner $(x,y)$ with $x > 0$ and $0 \le y < 1/x$. Let $t=t(x,y)$ be the side length of the largest square whose lower-left corner is $(x,y)$ and whose sides remain parallel to the axes....

Detailed mathematical approach

Problem Summary

The region of the problem is the set of points $(x,y)$ with $x\ge1$ and $0\le y\le1/x$, the area under the hyperbola $y=1/x$ to the right of the line $x=1$. Squares with horizontal and vertical sides, as in the figure of the statement, are placed into it one after another: $S_1$ is the largest square that fits under the curve, $S_2$ the largest square that fits into the uncovered rest, and so on. The index of $S_n$ is the pair formed by the number of squares to the left of $S_n$ and the number of squares below it. $S_2$ has the index $(1,0)$, $S_{32}$ and $S_{50}$ both have the index $(1,1)$, and $50$ is the largest $n$ with index $(1,1)$. We must find the largest $n$ for which $S_n$ has the index $(3,3)$. ^[1]

The whole solution in one sentence: every square fills the corner of a curved piece of the uncovered area and leaves a piece to its right and one above it, so the squares form a binary tree in which the index counts the steps right and up on a square's path; exactly $\binom63=20$ squares have the index $(3,3)$, and a priority queue that always takes out the largest waiting square lists $S_1,S_2,\dots$ until the last of them appears.

Mathematical Approach

We find the largest square in a corner, show that the rule only places such corner squares, and read the index and the order of the squares off the resulting tree.

1. The largest square in a corner

For a point $(x,y)$ with $x\ge1$, $y\ge0$ and $xy\lt1$, let $H(x,y)$ be the part of the region above and to the right of it: the points $(X,Y)$ with $X\ge x$, $Y\ge y$ and $XY\le1$. The whole region is $H(1,0)$. A square with lower-left corner $(a,b)$ and side $s$ lies in $H(x,y)$ exactly when $a\ge x$, $b\ge y$ and $(a+s)(b+s)\le1$, because the product $XY$ of positive coordinates is largest at the upper-right corner. Since $(a+s)(b+s)\ge(x+s)(y+s)$, every such square satisfies

$$(x+s)(y+s)\le1.$$

The left side grows with $s$, so $s\le t$, where $t=t(x,y)$ is the positive solution of $(x+t)(y+t)=1$, and $s=t$ forces $a=x$ and $b=y$. So $H(x,y)$ has exactly one largest square, its corner square, with lower-left corner $(x,y)$, side $t(x,y)$ and upper-right corner on the curve. Multiplied out, the condition reads $t^2+(x+y)t+xy-1=0$. The product of the two roots is $xy-1\lt0$, so exactly one root is positive, ^[2] and since $(x+y)^2-4(xy-1)=(x-y)^2+4$,

$$t(x,y)=\frac{\sqrt{(x-y)^2+4}-(x+y)}{2}.$$

For $S_1$, $x=1$ and $y=0$ give $t^2+t-1=0$ and $t=(\sqrt5-1)/2\approx0.618034$, which is $1/\varphi=\varphi-1$ for the golden ratio $\varphi=(1+\sqrt5)/2$. ^[3] The upper-right corner of $S_1$ is the point $(\varphi,1/\varphi)$ of the curve.

2. One square leaves two corners

Place the corner square $[x,x+t]\times[y,y+t]$ in $H(x,y)$. A point of $H(x,y)$ outside it has $X\gt x+t$, and then it lies in $H(x+t,y)$, the piece to the right of the square, or $Y\gt y+t$, and then it lies in $H(x,y+t)$, the piece above it; squares may touch, so every piece keeps its boundary. A point of both pieces has $XY\ge(x+t)(y+t)=1$, so the two pieces touch only at the upper-right corner of the square. Their corners lie strictly below the curve, since $(x+t)y$ and $x(y+t)$ are smaller than $1$. For $S_1$ the two pieces are $H(\varphi,0)$, because $1+1/\varphi=\varphi$, and $H(1,1/\varphi)$, the curved triangle above $S_1$.

3. The rule only places corner squares

Suppose that the uncovered area is a union of pieces $H(x_1,y_1),\dots,H(x_m,y_m)$, as it is at the start with the single piece $H(1,0)$, and that a square with lower-left corner $(a,b)$ and side $s$ fits into it. The corner $(a,b)$ lies in one of the pieces, say $H(x_i,y_i)$, and the upper-right corner lies under the curve, so

$$(x_i+s)(y_i+s)\le(a+s)(b+s)\le1$$

and $s\le t(x_i,y_i)$ by Section 1. This uses only two corners of the square, so it also covers squares that reach across several pieces. The largest square that fits is therefore the corner square of the piece with the largest $t$, and it is unique unless two pieces share this value; the statement takes this uniqueness for granted at every step, and the checks at the end confirm it up to the target. Placing it replaces its piece by the two pieces of Section 2, so the argument repeats: every $S_n$ is the corner square of a waiting piece.

4. A binary tree of squares

Each square therefore has two children, the corner squares of the pieces to its right and above it. With $\mathtt R$ for a step to the right child and $\mathtt U$ for a step to the upper child, every square is described by its path from $S_1$: $S_2$ is $\mathtt R$, the square above $S_1$ is $\mathtt U$, and $\mathtt{UR}$ lies to the right of $\mathtt U$. The rule keeps the waiting squares, at first $S_1$ alone, and repeatedly takes out the largest as the next $S_n$ and puts in its two children: the job of a priority queue, usually a binary heap. ^[4]

5. Children are smaller, so the squares come in order of size

The product $(x+t)(y+t)$ grows strictly with $x$, $y$ and $t$. If $x$ or $y$ grows, $t$ must therefore shrink to keep the product equal to $1$, and since the children have the corners $(x+t,y)$ and $(x,y+t)$, both are strictly smaller than their parent. Two consequences follow.

Decreasing order. When $S_n$ is taken out, every square not taken out yet is a waiting square or a descendant of one (the first square on its path that has not been taken out is waiting), and descendants are smaller. So the squares come out in decreasing order of size, and $n-1$ is the number of squares larger than $S_n$. Two squares of equal side would both be waiting when the first is taken out, so the assumption of Section 3 rules out equal sides.
Every square gets a number. A square of side $s$ with corner $(x,y)$ has $x+s\le1/(y+s)\le1/s$, so the squares of side at least $s$ lie where $X\le1/s$, in an area of $\int_1^{1/s}dX/X=\ln(1/s)$. ^[5] They do not overlap and each covers at least $s^2$, so there are at most $\ln(1/s)/s^2$ of them: for $s=0.1$ the bound is about $230$, and in fact there are $53$. By induction along its path, every square is therefore taken out after finitely many steps.

6. The index counts the steps

Claim: a square whose path has $L$ letters $\mathtt R$ and $B$ letters $\mathtt U$ has the index $(L,B)$.

Proof. Along the path, the $x$-coordinate of the corner starts at $1$, grows by the current side at each $\mathtt R$ and stays at each $\mathtt U$. So the $L$ squares from which the path steps right have $x$-intervals that follow each other without gaps from $X=1$ to the final square. After such a step from a square with corner $(x',y')$ and side $t'$, the path stays in $H(x'+t',y')$, whose points have $y'\le Y\le1/(x'+t')=y'+t'$, the height range of that square. A horizontal line through the inside of the final square therefore crosses, to the left, these $L$ squares, which cover the whole way to $X=1$, and no other square. The steps $\mathtt U$ and a vertical line give the $B$ squares below. $\square$

So the index is well defined. For example, $\mathtt{UR}$ has $\mathtt U$ to its left and $S_1$ below it, and $\mathtt{RU}$ has $S_1$ to its left and $S_2$ below it.

7. Twenty squares have the index (3,3)

By Section 6 the squares with index $(L,B)$ correspond to the words with $L$ letters $\mathtt R$ and $B$ letters $\mathtt U$, the lattice paths with $L$ steps to the right and $B$ steps up. Choosing the places of the letters $\mathtt R$ gives ^[6]

$$N(L,B)=\binom{L+B}{L}$$

such squares: the two squares $\mathtt{RU}$ and $\mathtt{UR}$ for $(1,1)$, and $\binom63=20$ squares, from $\mathtt{RRRUUU}$ to $\mathtt{UUURRR}$, for $(3,3)$. By Section 5 the requested $n$ belongs to the smallest of the twenty, and it is one more than the number of squares larger than that one.

8. Worked example: the first fifty squares

Decimals here are rounded to six places. The squares along the bottom have the corners $(x_k,0)$ with $x_0=1$ and the indices $(k,0)$. Their sides satisfy $(x_k+t_k)\,t_k=1$ and $x_{k+1}=x_k+t_k$, so $t_k=1/x_{k+1}$, $x_k=x_{k+1}-1/x_{k+1}$ and

$$x_{k+1}^2-x_k^2=(x_{k+1}+x_k)\,t_k=2-\frac{1}{x_{k+1}^2}.$$

Each step adds between $1$ and $2$ to $x_k^2$, at first $1.618034$, $1.772223$ and $1.839480$. As $x_k^2\ge k+1$ grows without bound, the increments tend to $2$, so $x_k^2/(2k)$ tends to $1$, and the sides shrink slowly, roughly like $1/\sqrt{2k}$: $t_0\approx0.618034$, $t_1\approx0.477260$, $t_2\approx0.400650$, $t_3\approx0.351226$. The square $\mathtt U$, with corner $(1,1/\varphi)$, has the side $0.209057$, between $t_{10}\approx0.214999$ and $t_{11}\approx0.205885$. So $S_1,\dots,S_{11}$ are the bottom squares with the indices $(0,0)$ to $(10,0)$, and $S_{12}=\mathtt U$ has the index $(0,1)$.

The square $\mathtt{UR}$, with corner $(1.209057,0.618034)$, has the side $0.129204$, between $t_{29}\approx0.130037$ and $t_{30}\approx0.127910$, so it is $S_{32}$, after $30$ bottom squares and $\mathtt U$. The square $\mathtt{RU}$, with corner $(1.618034,0.477260)$, has the side $0.103588$, between $t_{46}\approx0.103743$ and $t_{47}\approx0.102650$, so it is $S_{50}$, after $47$ bottom squares, $\mathtt U$ and $\mathtt{UR}$. All other squares are smaller: $\mathtt{UU}$ has the side $0.090185$, the children of $\mathtt{UR}$ have $0.084717$ and $0.048166$, and the square above the bottom square $(k,0)$, with corner $(x_k,t_k)$ and $x_k=1/t_k-t_k$, has a side $u$ with $u^2+u/t_k=t_k^2$, which shrinks with $t_k$: it is $0.062736$ above $(2,0)$ and less further right. The rest descend from these squares or from $\mathtt{RU}$. By Sections 6 and 7, $\mathtt{UR}$ and $\mathtt{RU}$ are the only squares with index $(1,1)$, so $50$ is the largest such $n$, as the statement says.

9. Small cases and the twenty target squares

Write $A(L,B)$ for the largest $n$ with index $(L,B)$. Running the rule gives:

$A(0,0)=1$, $A(1,0)=2$, $A(2,0)=3$;
$A(0,1)=12$, $A(1,1)=50$, $A(2,1)=134$;
$A(0,2)=66$, $A(1,2)=716$, $A(2,2)=4014$.

Steps up cost more than steps to the right, because the pieces above the bottom squares are flat: for $k\ge1$ the piece above $(k,0)$ is $t_k$ wide and $t_{k-1}-t_k$ high, as $1/x_k=t_{k-1}$, which is $0.400650$ by $0.076610$ above $(2,0)$. The twenty target squares range from $\mathtt{URURUR}$, with side about $0.006988$, down to $\mathtt{RRRUUU}$, with side about $0.000801377$, which runs three steps along the bottom and climbs three steps into the flat piece above $S_4$.

10. How precise the arithmetic must be

For a small square far to the right, the two terms of the formula in Section 1 are nearly equal, and their difference loses digits; along the bottom, $\sqrt{x^2+4}-x\approx2/x$. The side of $\mathtt{RRRUUU}$ exceeds $0.000801376$, so by Section 5 every square at least as large has $x\lt1/0.000801376\lt1248$, and about six of the sixteen digits of double precision can be lost. Measured against a recomputation with $60$ digits, the computed sides are off by at most $10^{-10}$ of their size; the equivalent form ^[7]

$$t(x,y)=\frac{2(1-xy)}{\sqrt{(x-y)^2+4}+x+y}$$

avoids the subtraction and lowers this to about $1.5\cdot10^{-13}$. The first form, used by the programs, is enough: only comparisons with $\mathtt{RRRUUU}$ matter (Section 7), and its neighbours in the order differ from it by about $1.5\cdot10^{-7}$ and $4.9\cdot10^{-7}$ of its side, over a thousand times the measured error.

How the Code Works

In the C++ program, ^[8] parse_arguments reads --left= and --below=, which replace the default target $(3,3)$, and --skip-checkpoints; without the latter, run_checkpoints first requires the $50$ of the statement for the index $(1,1)$ (exit code $2$ otherwise), and main prints the result of solve.

A waiting square is a Node with the counters left and below, the corner x, y and the side side. largest_side evaluates the formula of Section 1, and binom computes $\binom nk$ in 64-bit unsigned integers as $(n-k'+1)\cdots n$ divided by $k'!$ with $k'=\min(k,n-k)$, exact while the product fits into 64 bits, as for the target: $4\cdot5\cdot6/6=20$. solve sets target_occurrences to $\binom{L+B}{L}$ from Section 7 and uses a std::priority_queue ordered by side, so that top() is the largest waiting square. ^[9] Starting from the corner square of $(1,0)$, each pass takes out the top node and increases index, its number $n$ by Section 5; if the node has the target index, seen grows and answer becomes index; then the right child, with left one larger and corner $(x+t,y)$, and the upper child, with below one larger and corner $(x,y+t)$, are pushed. When seen reaches target_occurrences, the smallest target square has just come out, and answer is its number.

The Python and Java versions run the same loop without a checkpoint: Python's solve takes the target as parameters with defaults $(3,3)$, Java's fixes it, and both return a string, counting with unbounded Python integers or 64-bit Java long. Python's heapq is a min-heap that compares only with <, so Node.__lt__ returns self.side > other.side; Java's PriorityQueue returns its least element, so compareTo uses Double.compare(other.side, this.side). ^[9] Both use 64-bit IEEE doubles. The C++ long double is the 80-bit extended format with most x86 compilers but has the format of double with others, such as Microsoft's and those for 64-bit ARM under macOS; ^[10] by the checks of Section 10, double precision suffices here.

Complexity and Verification

Let $A$ be the requested $n$. The loop takes out $A$ squares and adds two for each, so the queue holds $k+1$ nodes after $k$ steps, and each push or pop costs $O(\log A)$. ^[4] The time is $O(A\log A)$ and the memory $O(A)$ nodes; in our test on a desktop computer, C++ and Java took about $0.1$ s and Python about $1.5$ s. A heap is not even necessary: by Section 5 the requested $n$ is the number of squares at least as large as $\mathtt{RRRUUU}$, and a depth-first search that skips the subtree below every smaller square counts them in $O(A)$ steps.

Besides the checkpoint of the C++ program, these checks, not part of the published solutions, were run for this article:

The C++ program (built with GCC and with Clang), the Python and Java programs and a separate Python heap print the same number; the C++ options and that heap agree on $A(L,B)$ for all $L,B\le3$ except the target.
For the first $3000$ squares, every upper-right corner lies on the curve, no two squares overlap, and lines to the left and downwards meet as many squares as the path has letters $\mathtt R$ and $\mathtt U$ (Section 6).
The depth-first count gives the same $n$ as the heap.
A heap with $60$ significant digits takes out the same squares in the same order as the double-precision programs, up to the last square with index $(3,3)$; consecutive sides in this list differ by at least $6.9\cdot10^{-12}$ of their size, while a $100$-digit recomputation changes them by less than $10^{-55}$, so no two of these squares tie. Heaps with significands of $53$, $64$ and $113$ bits (double, x86 extended and quadruple precision) give the same $n$.

Footnotes and References

The references supply background facts; the corner squares, the splitting and the index rule are proved in this article, and the precision of the computation is checked numerically.

Project Euler 247 — Squares Under a Hyperbola. The official statement fills the region 1 ≤ x, 0 ≤ y ≤ 1/x step by step with largest squares S₁, S₂, …, defines the index of Sₙ by the squares to its left and below it, gives the index (1, 0) of S₂ and (1, 1) of S₃₂ and S₅₀, the last such n, and asks for the largest n with index (3, 3).
Wikipedia — Vieta's formulas. The roots of ax² + bx + c satisfy r₁ + r₂ = −b/a and r₁r₂ = c/a; in Section 1 the product is xy − 1 < 0, so the roots have opposite signs.
Wikipedia — Golden ratio. φ = (1 + √5)/2 satisfies φ² = φ + 1, and 1/φ = φ − 1 ≈ 0.618, the side of S₁.
Wikipedia — Binary heap. Binary heaps are a common way of implementing priority queues; insertion and extraction of the top element take O(log n) time in the worst case.
Wikipedia — Natural logarithm. ln a is the area under the curve y = 1/x from 1 to a, which bounds the number of large squares in Section 5.
Wikipedia — Lattice path. The number of lattice paths from (0, 0) to (n, k) with unit steps to the right and up is the binomial coefficient C(n + k, n).
D. Goldberg, What Every Computer Scientist Should Know About Floating-Point Arithmetic, ACM Computing Surveys, 1991. Its section on cancellation shows how the quadratic formula loses accuracy for the smaller root and cures this with the conjugate of the numerator.
C++ — Euler247.cpp. The linked immutable revision contains largest_side, binom, solve and run_checkpoints; it is the implementation record for this article.
cppreference — std::priority_queue: top() is the largest element by default. Python — heapq: heap[0] is the smallest item, and items are compared only with <. Java — PriorityQueue: the head is the least element; offer and poll take O(log n) time.
Wikipedia — long double. Most x86 compilers implement long double as the 80-bit extended format; with Microsoft Visual C++ and on 64-bit ARM under Windows and macOS it has the format of double.

Problem 247 source code

C++

#include <cmath>
#include <cstdint>
#include <functional>
#include <iostream>
#include <queue>
#include <string>

namespace {

using u64 = std::uint64_t;

struct Options {
    int target_left = 3;
    int target_below = 3;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(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_int_after_prefix(arg, "--left=", options.target_left) ||
            parse_int_after_prefix(arg, "--below=", options.target_below)) {
            continue;
        }

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

    return options.target_left >= 0 && options.target_below >= 0;
}

struct Node {
    int left = 0;
    int below = 0;
    long double x = 1.0L;
    long double y = 0.0L;
    long double side = 0.0L;
};

long double largest_side(const long double x, const long double y) {
    // Solve y + t = 1/(x + t) for t>0.
    return (std::sqrt((x - y) * (x - y) + 4.0L) - (x + y)) / 2.0L;
}

u64 binom(const int n, const int k) {
    if (k < 0 || k > n) {
        return 0;
    }
    if (k == 0 || k == n) {
        return 1;
    }
    u64 numer = 1;
    u64 denom = 1;
    const int kk = std::min(k, n - k);
    for (int i = 1; i <= kk; ++i) {
        numer *= static_cast<u64>(n - kk + i);
        denom *= static_cast<u64>(i);
    }
    return numer / denom;
}

u64 solve(const int target_left, const int target_below) {
    const u64 target_occurrences = binom(target_left + target_below, target_left);

    auto cmp = [](const Node& a, const Node& b) {
        return a.side < b.side;
    };
    std::priority_queue<Node, std::vector<Node>, decltype(cmp)> pq(cmp);

    Node root;
    root.left = 0;
    root.below = 0;
    root.x = 1.0L;
    root.y = 0.0L;
    root.side = largest_side(root.x, root.y);
    pq.push(root);

    u64 index = 0;
    u64 seen = 0;
    u64 answer = 0;

    while (seen < target_occurrences) {
        const Node cur = pq.top();
        pq.pop();

        ++index;
        if (cur.left == target_left && cur.below == target_below) {
            ++seen;
            answer = index;
        }

        Node right;
        right.left = cur.left + 1;
        right.below = cur.below;
        right.x = cur.x + cur.side;
        right.y = cur.y;
        right.side = largest_side(right.x, right.y);
        pq.push(right);

        Node up;
        up.left = cur.left;
        up.below = cur.below + 1;
        up.x = cur.x;
        up.y = cur.y + cur.side;
        up.side = largest_side(up.x, up.y);
        pq.push(up);
    }

    return answer;
}

bool run_checkpoints() {
    if (solve(1, 1) != 50ULL) {
        std::cerr << "Checkpoint failed for index (1,1)" << '\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.target_left, options.target_below) << '\n';
    return 0;
}

Python

import math
import heapq

def largest_side(x, y):
    # Solve y + t = 1/(x + t) for t > 0
    return (math.sqrt((x - y)**2 + 4.0) - (x + y)) / 2.0

def binom(n, k):
    if k < 0 or k > n: return 0
    if k == 0 or k == n: return 1
    numer = 1
    denom = 1
    kk = min(k, n - k)
    for i in range(1, kk + 1):
        numer *= (n - kk + i)
        denom *= i
    return numer // denom

class Node:
    def __init__(self, left, below, x, y, side):
        self.left = left
        self.below = below
        self.x = x
        self.y = y
        self.side = side
        
    def __lt__(self, other):
        # We want a max-heap based on side, so return True if self.side > other.side
        return self.side > other.side

def solve(target_left=3, target_below=3):
    target_occurrences = binom(target_left + target_below, target_left)
    
    pq = []
    
    root_x = 1.0
    root_y = 0.0
    root_side = largest_side(root_x, root_y)
    root = Node(0, 0, root_x, root_y, root_side)
    
    heapq.heappush(pq, root)
    
    index = 0
    seen = 0
    answer = 0
    
    while seen < target_occurrences:
        cur = heapq.heappop(pq)
        index += 1
        
        if cur.left == target_left and cur.below == target_below:
            seen += 1
            answer = index
            
        right_x = cur.x + cur.side
        right_y = cur.y
        right_side = largest_side(right_x, right_y)
        right = Node(cur.left + 1, cur.below, right_x, right_y, right_side)
        heapq.heappush(pq, right)
        
        up_x = cur.x
        up_y = cur.y + cur.side
        up_side = largest_side(up_x, up_y)
        up = Node(cur.left, cur.below + 1, up_x, up_y, up_side)
        heapq.heappush(pq, up)
        
    return str(answer)

if __name__ == '__main__':
    print(solve())

Java

import java.util.PriorityQueue;

public class Euler247 {
    static class Node implements Comparable<Node> {
        int left, below;
        double x, y, side;

        Node(int left, int below, double x, double y, double side) {
            this.left = left;
            this.below = below;
            this.x = x;
            this.y = y;
            this.side = side;
        }

        @Override
        public int compareTo(Node other) {
            // Max-heap based on side lengths mapping to highest priority
            return Double.compare(other.side, this.side);
        }
    }

    static double largestSide(double x, double y) {
        return (Math.sqrt((x - y) * (x - y) + 4.0) - (x + y)) / 2.0;
    }

    static long binom(int n, int k) {
        if (k < 0 || k > n)
            return 0;
        if (k == 0 || k == n)
            return 1;
        long numer = 1;
        long denom = 1;
        int kk = Math.min(k, n - k);
        for (int i = 1; i <= kk; ++i) {
            numer *= (n - kk + i);
            denom *= i;
        }
        return numer / denom;
    }

    public static String solve() {
        int targetLeft = 3;
        int targetBelow = 3;

        long targetOccurrences = binom(targetLeft + targetBelow, targetLeft);

        PriorityQueue<Node> pq = new PriorityQueue<>();

        double rootX = 1.0;
        double rootY = 0.0;
        double rootSide = largestSide(rootX, rootY);
        pq.add(new Node(0, 0, rootX, rootY, rootSide));

        long index = 0;
        long seen = 0;
        long answer = 0;

        while (seen < targetOccurrences) {
            Node cur = pq.poll();
            index++;

            if (cur.left == targetLeft && cur.below == targetBelow) {
                seen++;
                answer = index;
            }

            double rightX = cur.x + cur.side;
            double rightY = cur.y;
            double rightSide = largestSide(rightX, rightY);
            pq.add(new Node(cur.left + 1, cur.below, rightX, rightY, rightSide));

            double upX = cur.x;
            double upY = cur.y + cur.side;
            double upSide = largestSide(upX, upY);
            pq.add(new Node(cur.left, cur.below + 1, upX, upY, upSide));
        }

        return String.valueOf(answer);
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}