Detailed mathematical approach

Problem Summary

A positive integer \(N\) is called stealthy if there exist positive integers \(a,b,c,d\) such that

$ab=cd=N,\qquad a+b=c+d+1.$

The task is to count how many distinct stealthy numbers satisfy \(N\le L\). The key fact used by the implementation is that stealthy numbers are exactly the products of two pronic numbers.

Mathematical Approach

Define the pronic function

$P(t)=t(t+1).$

The whole problem becomes manageable once we show that every stealthy number can be written as \(P(x)P(y)\), and then enumerate those products without double-counting repeats.

Step 1: Convert the Definition into a Product Formula

Take two factor pairs of the same stealthy number, and let \((a,b)\) be the pair with the larger sum. After ordering the factors, the other pair lies strictly between them, so we may write

$c=a+k,\qquad d=b-k-1,\qquad k\ge 1.$

The condition \(ab=cd\) becomes

$ab=(a+k)(b-k-1)=ab+k(b-a-k-1)-a.$

Hence

$a=k(b-a-k-1).$

So \(k\) divides \(a\). Write

$a=ky,\qquad y\ge 1.$

Substituting back gives

$b=(k+1)(y+1),\qquad c=k(y+1),\qquad d=(k+1)y.$

Therefore

$N=ab=k(k+1)y(y+1).$

Renaming \(k\) as \(x\), we obtain the standard parametrization

$\boxed{N=x(x+1)y(y+1).}$

Step 2: Prove the Converse and Remove the Symmetry

The formula above is not only necessary but also sufficient. For any positive integers \(x\) and \(y\), consider the two factor pairs

$xy\cdot (x+1)(y+1),\qquad x(y+1)\cdot y(x+1).$

Both products equal

$x(x+1)y(y+1),$

and their sums differ by exactly \(1\):

$xy+(x+1)(y+1)=x(y+1)+y(x+1)+1.$

So every number of the form \(x(x+1)y(y+1)\) is stealthy. The counting problem is therefore equivalent to counting distinct products

$P(x)P(y),\qquad x,y\ge 1.$

Because \(P(x)P(y)=P(y)P(x)\), we may impose

$1\le x\le y$

to remove the obvious symmetry.

Step 3: Bound the Valid Search Region

For a fixed \(x\), admissible values of \(y\) satisfy

$P(x)P(y)\le L,$

or equivalently

$P(y)\le \left\lfloor\frac{L}{P(x)}\right\rfloor.$

If we define

$T_x=\left\lfloor\frac{L}{P(x)}\right\rfloor,$

then \(y\) must solve

$y(y+1)\le T_x.$

The positive root of \(y^2+y-T_x=0\) is

$\frac{-1+\sqrt{1+4T_x}}{2},$

so the largest valid integer is

$y_{\max}(x)=\left\lfloor\frac{\sqrt{1+4T_x}-1}{2}\right\rfloor.$

There is also a bound on \(x\) itself. Since \(y\ge x\), the smallest product in the \(x\)-row is \(P(x)^2\), so that row is active only when

$P(x)^2\le L.$

This determines the final range of rows that must be explored.

Step 4: View the Candidates as Sorted Lists

For each active \(x\), define the list

$V_x=\{P(x)P(y): y=x,x+1,\dots,y_{\max}(x)\}.$

Because \(P(y)\) is strictly increasing, every \(V_x\) is strictly increasing as well. The full set of candidates is the union of these sorted lists. That means the problem is no longer a brute-force scan over all pairs; it is a k-way merge problem over many already sorted sequences.

Step 5: Merge the Lists and Deduplicate Online

A min-heap stores the current first unseen value from each list \(V_x\). Repeatedly removing the smallest heap element produces the global candidate stream in increasing order. When a value from one row is consumed, the next product from the same row is inserted.

Duplicates can occur because the same stealthy number may have more than one parametrization. Since the merged stream is sorted, equal products appear consecutively, so it is enough to compare the current extracted value with the previously extracted one:

$v_{\mathrm{current}}\ne v_{\mathrm{previous}}.$

This is why the implementation can count distinct stealthy numbers without storing every product in a global set.

Worked Example: \(L=200\)

First compute the relevant pronic numbers:

$P(1)=2,\quad P(2)=6,\quad P(3)=12,\quad P(4)=20.$

Since \(P(4)^2=400>200\), only the rows \(x=1,2,3\) are active.

For \(x=1\), we need \(2P(y)\le 200\), so \(P(y)\le 100\) and \(y_{\max}(1)=9\). This row is

$4,12,24,40,60,84,112,144,180.$

For \(x=2\), we need \(6P(y)\le 200\), so \(P(y)\le 33\) and \(y_{\max}(2)=5\). This row is

$36,72,120,180.$

For \(x=3\), only \(y=3\) works, giving

$144.$

Merging and deduplicating yields

$4,12,24,36,40,60,72,84,112,120,144,180,$

so there are \(12\) stealthy numbers up to \(200\). The repeated values \(144\) and \(180\) show why deduplication is necessary.

How the Code Works

The C++, Python, and Java implementations first build a table of pronic numbers up to the global limit \(P(y)\le L\). They then determine which starting rows are active by checking whether \(P(x)^2\le L\).

For every active row, the implementation computes the exact upper bound \(y_{\max}(x)\) using the inverse-pronic formula above and inserts the first value \(P(x)^2\) into a priority queue. Each queue entry stores enough information to generate the next product from the same row.

The main loop repeatedly removes the smallest current product. If it differs from the previous extracted value, the answer is increased by \(1\). Then the row that produced that product is advanced from \(y\) to \(y+1\), and the new product is inserted if it still lies within the valid range. The C++ version maintains its own binary heap, while the Python and Java versions rely on standard library priority queues, but the algorithmic idea is the same in all three languages.

Complexity Analysis

Let

$K=\#\{x:P(x)^2\le L\},\qquad M=\sum_{x=1}^{K}\bigl(y_{\max}(x)-x+1\bigr).$

Building the pronic table up to the global bound costs \(O(\sqrt{L})\) time and \(O(\sqrt{L})\) memory, because the largest needed index satisfies \(P(y)\le L\). The priority-queue phase performs one extract operation and at most one insert operation per generated pair, so it costs \(O(M\log K)\) time and \(O(K)\) additional memory for the heap.

In particular, the implementation never stores all \(M\) products at once. It keeps only one current candidate per active row, which is the essential reason the method remains practical for very large limits.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=757
2. Pronic number: Wikipedia — Pronic number
3. Integer square root: Wikipedia — Integer square root
4. Priority queue: Wikipedia — Priority queue
5. K-way merge algorithm: Wikipedia — K-way merge algorithm