Finding $z=x+y$ such that $x^2 + y^2$ is prime For which integers $z$ can one write $z=x+y$ such that $x^2+y^2$ is prime?
It feels like it should be possible for all odd $z>1$, and I have tried to adapt Euler's proof of Girard/Fermat's assertion that any prime congruent to $1 \bmod 4$ can be uniquely expressed as the sum of two squares, but without success.
 A: Heuristic analysis shows that it's highly likely that your conjecture holds for all odd $z$.
Take an arbitrary odd number $z=2n+1$. The pair of numbers $x,y$ such that $x+y=z=2n+1$ has the minimum sum of squares equal to:
$$s_1=n^2+(n+1)^2=2n^2+2n+1$$
...and the maximum sum:
$$s_2=1^2+(2n)^2=4n^2+1$$ 
All sums of squares $x^2+y^2$ fall into segment $[s_1,s_2]$ and there are $n$ such sums, from $x=1,y=2n$ up to $x=n,y=n+1$. 
The number of primes between $s_1$ and $s_2$ is equal to:
$$n_p=\pi(s_2)-\pi(s_1)$$ and probability that a randomly selected number between $s_1$ and $s_2$ is a prime is approximately:
$$p_n=\frac{\pi(s_2)-\pi(s_1)}{s_2-s_1}=\frac{\pi(4n^2+1)-\pi(2n^2+2n+1)}{2n(n-1)}$$
You have $n$ different sums of squares between $s_1$ and $s_2$ and chances that all of them are composite are approximately:
$$P_n=(1-p_n)^n$$
$$P_n=\left[1-\frac{\pi(4n^2+1)-\pi(2n^2+2n+1)}{2n(n-1)}\right]^n$$
The value of $P_n$ drops sharply when $n$ increases. For example:
$$P_{10}=0.141219$$
$$P_{20}=0.0495773$$
$$P_{100}=0.0000375915$$
$$P_{500}=2.12378\times 10^{-17}$$
$$P_{1000}=6.7996\times 10^{-31}$$
$$P_{10000}=2.23594\times 10^{-229}$$
This proves nothing but is in sync with my numeric experiment that went all the way up to $n=10^7$. It shows that $x^2+y^2$ becomes prime for the first time for comparatively small values of $x$ ($x<<<z$). 
Actually, if you plot the smallest value of $x/z$ for which $x^2+(z-x)^2$ is a prime you get a pretty fascinating graph:
 
Notice how small the ratio $x/z$ really is. One could conjecture that:
$$\lim_{z\to\infty} \frac{x_{min}}{z}=0$$
