Problem can be solved using quadratic congruence solver. We can check for prime p which values greater than p such n^2 + a are divisible by prime p. In this way we greatly reduce search space by obtaining exluded values for given number % prime. Primes up to 97 is sufficient.

answer of investigation prime patter

what are the prime patterns less than 1 million

It looks like part of your system isn't working as it should, because I keep submitting the same code and get 1 or 2 timeouts, but always on different test cases.

Are there any such N`s less than 10,000? Please