Project Euler Problem 757
A positive integer N is stealthy, if there exist positive integers a, b, c, d such that ab = cd = N and a+b = c+d+1.
Solution
Answer: 75737353
A stealthy number has the characterization
$$N = x(x+1)y(y+1)$$
for positive integers $x,y$. Indeed, setting
$$a=xy,\quad b=(x+1)(y+1),\quad c=x(y+1),\quad d=(x+1)y$$
gives
$$ab = cd = x(x+1)y(y+1)$$
and
$$a+b = c+d+1.$$
So the problem reduces to counting distinct integers of the form
$$x(x+1)y(y+1)\le 10^{14}.$$
A direct set-based approach is too memory-intensive, but we can exploit the fact that for fixed $x$, the sequence in $y$ is increasing. There are only $3162$ possible $x$-values (since $x(x+1)^2 \le 10^{14}$), so we can treat each $x$-sequence as a sorted list and perform a k-way merge with a heap, counting unique values exactly.
Verification on the given check:
- For $10^6$, the method returns 2851, matching the problem statement.
Running the exact computation for $10^{14}$ gives:
Answer: 75737353