Solution

Answer: 782252

Let a region $R(a,b)$ be defined by

$$x\ge a,\qquad y\ge b,\qquad y\le \frac1x,$$

where the corner $(a,b)$ lies below the hyperbola $xy=1$.

Inside such a region, the largest axis-aligned square has lower-left corner $(a,b)$ and side length $s$ determined by the condition that its upper-right corner lies on the curve:

$$(a+s)(b+s)=1.$$

Expanding,

$$s^2 + (a+b)s + ab - 1 = 0.$$

Taking the positive root,

$$s(a,b)=\frac{\sqrt{(a-b)^2+4}-(a+b)}{2}.$$

For the original problem, we start with

$$(a,b)=(1,0).$$

The first square $S_1$ therefore has side

$$s=\frac{\sqrt5-1}{2}.$$

Recursive structure

After placing a square of side $s$ in $R(a,b)$, two disjoint regions remain:

the region to the right:

$$R(a+s,b),$$

the region above:

$$R(a,b+s).$$

If the current square has index $(L,B)$, then:

the right child has index $(L+1,B)$,
the upper child has index $(L,B+1)$.

Thus every square corresponds to a path of Right/Up moves.

For example, index $(3,3)$ corresponds to all paths containing exactly three rights and three ups, so there are

$$\binom63 = 20$$

such squares in total.

Ordering of squares

The squares are numbered globally by decreasing side length.

Therefore:

generate squares in descending order of side,
whenever a square with index $(3,3)$ appears, record its position $n$,
the largest such $n$ is the answer.

A priority queue (max-heap) is ideal.

Python implementation

from heapq import heappush, heappop
from math import sqrt, comb

def side(a, b):
    """
    Side length of the largest square that fits in region R(a,b).
    Derived from:
        (a+s)(b+s) = 1
    """
    return (sqrt((a - b) ** 2 + 4) - (a + b)) / 2

def solve(target=(3, 3)):
    # Number of squares having this index
    needed = comb(target[0] + target[1], target[0])

    # Max-heap implemented with negative sizes
    pq = []

    # Initial region R(1,0)
    s0 = side(1.0, 0.0)

    # heap item = (-side, a, b, left, below)
    heappush(pq, (-s0, 1.0, 0.0, 0, 0))

    n = 0
    found = []

    smallest_target_size = float("inf")

    while pq:
        neg_s, a, b, left, below = heappop(pq)
        s = -neg_s

        n += 1

        # Record squares with desired index
        if (left, below) == target:
            found.append((n, s))
            smallest_target_size = min(smallest_target_size, s)

            # Once all target squares are found,
            # we can stop when remaining squares are smaller
            if len(found) == needed:
                if -pq[0][0] < smallest_target_size:
                    break

        # Generate right child
        sr = side(a + s, b)
        heappush(pq, (-(sr), a + s, b, left + 1, below))

        # Generate upper child
        su = side(a, b + s)
        heappush(pq, (-(su), a, b + s, left, below + 1))

    return found[-1][0]

answer = solve((3, 3))
print(answer)

Code walkthrough

1. `side(a,b)`

Computes the largest square fitting inside region $R(a,b)$:

$$(a+s)(b+s)=1.$$

The positive quadratic root gives the side length.

2. Priority queue

We always remove the currently largest square first, matching the problem’s numbering order.

Each heap item stores:

(-side, a, b, left, below)

where:

(a,b) identifies the region,
(left, below) is the square’s index.

3. Child regions

After placing a square:

(a+s, b)     # right region
(a, b+s)     # upper region

Their indices become:

(left+1, below)
(left, below+1)

4. Stopping criterion

For index $(3,3)$, there are exactly

$$\binom63 = 20$$

possible squares.

Once all 20 are found, and the largest remaining square in the heap is smaller than the smallest target square already found, no additional $(3,3)$ square can appear later.

Verification on the sample

Running the same code for target $(1,1)$ gives:

$$50$$

matching the statement:

“50 is the largest $n$ for which the index is $(1,1)$.”

So the algorithm is validated.

Final verification

The computation finds exactly 20 squares of index $(3,3)$, and the last one appears at:

$$n = 782252.$$

This is consistent with the rapidly growing number of larger squares generated before the smallest $(3,3)$ configuration appears.

Answer: 782252

Project Euler Problem 247