Question

Solutions of $x(y^2-x-1)=n$ are easy to enumerate assuming $n$ is factored. Appears a quadratic must have solutions $\mod \text{divisors of } \frac{n}{x}$ for each solution $(x,y)$. If this is correct is there an algorithm to choose the primes so the quadratic has solutions mod many divisors?

If one drops $-1$ the case is unbounded using the scaling $(x,y,n) \to (xd^2,yd,nd^4)$.

Current best is n= 148127975424000 with 30 positive solutions.

Answer 1

Since it is not known whether $x(y^2-x-1)=n$ can have an arbitrarily large number of integer solutions as $n$ varies, I doubt that there is an algorithm of the sort that you want. On the other hand, if you could prove that there is a sequence $n_1,n_2,\ldots$ such that the number of integer solutions to $x(y^2-x-1)=n_i$ goes to infinity, then the rank of the group of rational points would probably also go to infinity (it definitely would if one assumes the abc conjecture). However, here's a heuristic argument as to why the number of integer solutions is bounded. For any given $n$, we look at each divisor $d|n$, set $x=d$, and we get a solution (really two solutions) if and only if $d+n/d+1$ is a perfect square. The probability that this happens is $1/\sqrt{d+n/d+1}$. So the expected number of solutions is $$ \sum_{d|n} \frac{1}{\sqrt{d+n/d+1}}. \qquad(*) $$ We can estimate this sum by $$ \sum_{d|n} \frac{1}{\sqrt{d+n/d+1}} \le 2 \sum_{d|n,d\ge\sqrt{n}} \frac{1}{\sqrt{d}} \le 2\cdot\frac{1}{n^{1/4}}\cdot d(n), $$ where $d(n)$ is the number of divisors of $n$. A standard estimate shows that there is a constant $c$ such that $d(n)<n^{c/\log\log n}$ for all $n$. Hence the sum $(*)$ is bounded as $n$ varies over all positive integers.