Problem: Find integer $N$ such that it can NOT be expressed as $N=a^2+b^2+c^2$ or $N=a^2+b^2-c^2$ where integers $0<a^2,b^2,c^2\leq N$.
For $N<100000$ there should be only 17 such integers. What is the next $N$? Is there some algorithm that takes less than $O(N^3)$ to find such a number?
Let $a=\lfloor \sqrt N\rfloor $. If $N=a^2$ we have the trivial solutions $N=a^2+0^2\pm0^2$, so we assume $N\ne a^2$. Then $a^2+1\le N\le (a+1)^2-1=a^2+2a$, hence $1\le N-a^2\le 2a\le2\sqrt N$. If $N-a^2$ is odd or a multiple of $4$ we can write it as a product $N-a^2=uv$ with $u\equiv v\pmod 2$ and $v\in\{1,2\}$. Let $b=\frac{u+v}{2}$, $c=\frac{u-v}2$. Then $0\le c\le b\le \lfloor \frac{2a+1}{2}\rfloor = a$, hence $c^2\le b^2\le a^2\le N$ and $a^2+b^2-c^2=a^2+(b-c)(b+c)=a^2+uv=N$.
Remains the case $N-\lfloor \sqrt N\rfloor ^2\equiv 2\pmod 4$. Let $a=\lfloor \sqrt N\rfloor -1$. Then $(a+1)^2<N<(a+2)^2$ and $N-(a+1)^2\equiv 2\pmod 4$. Thus $2a+2\le N-a^2\le 4a+3$ and $N-a^2$ is odd. Unless $N-a^2$ is prime, we can write it as $uv$ with $u\ge v\ge 3$ and both odd. Again we can let $b=\frac{u+v}2$ and $c=\frac{u-v}2$and have $0\le c<b\le \frac{\frac{4a+3}{3}+3}{2}=\frac23 a+2$. Except for small $N$ this is $\le \sqrt N$ and gives a solution $N=a^2+b^2-c^2$.
Remains the case of $N$ with $N-\lfloor \sqrt N\rfloor ^2\equiv 2\pmod 4$ and $N-\lfloor \sqrt N-1\rfloor ^2$ prime. If you only have to test these cases, this may already speed things up a lot. To speed up the test for $N=a^2+b^2+c^2$, observe that $b^2+c^2$ is $0\pmod 4$ or $1\pmod 4$ or $2\pmod 8$ and is divisible by primes $\equiv 3\pmod 4$ only if by an even power ...