A conjecture about an unlimited path Conjecture:  
For all primes of the form $a^2+b^2$, there are natural numbers $s,t,u,v$ such that  


*

*$\quad s^2+t^2,u^2+v^2$ are primes

*$\quad a+b=s+t$

*$\quad u+v=s+t+2$

*$\quad |s-u|+|t-v|=2$


This conjecture implies Any odd number is of form $a+b$ where $a^2+b^2$ is prime and seems to be much stronger. I have tested it for $a+b<50.000$ without founding a counterexample, but I guess there may exist counterexamples.

In the diagram the vertices correspond to points $(x,y)$ where $x^2+y^2$ is prime, the red edges correspond to pairs of vertices with taxi cab distance equal to $2$ and the gray diagonal lines is the (taxi cab) equidistance lines to origin. 
The conjecture says there are paths following red edges and gray diagonal lines up to any distance from origin. 
Addendum: Further tests show that there exists red vertical edges that together with the gray diagonal lines make such paths for all odd $n=a+b=3,\dots,49,999$ except for $n\in\{9,19,49,75,149\}$.

In this case I want help with finding counterexamples.

 A: We first have:
$$2=|{u-s}|+|v-t| \geqslant (u-s)+(v-t)=(u+v)-(s+t)=2$$
Equality holds only when $|x|=x$. Since it does, we have:
$$u \geqslant s \space ; v \geqslant t \space ; u+v=s+t+2$$
These $3$ statements imply that the only possibilities to chose $u$ and $v$ from is:
$$(u,v)=(s+2,t),(s+1,t+1),(s,t+2)$$
Thus, we have completely made use of rules $(3)$ and $(4)$.

We know by Fermat's sum of two squares theorem that a prime can be written as the sum of two squares if and only if it is $1 \pmod{4}$. This representation is also unique. We can rewrite the conjecture as:

Define $S = \{(a,b) \space| \space a^2+b^2 \in \mathbb{P}\}$. For every $n
 \in \mathbb{N}$, if $\exists$ $(a,b) \in S \space ; a+b=n$, then
   $\exists$ $(s,t) \in S$ such that one of $(s+2)^2+t^2$,
   $(s+1)^2+(t+1)^2$, $s^2+(t+2)^2$ is prime.

Moreover, this implies that if $n$ is a possible sum of some pair $(a,b) \in S$, then so is $n+2$. By induction hypothesis, this implies that for any odd $n \in \mathbb{N}$, we can find $(a,b) \in S$ where $a+b=n$. Thus, we can again reformulate the conjecture as:

For every odd $n \in \mathbb{N}$ where $n>1$, $\exists$ $x \in \mathbb{N}$ such
   that $x^2+(n-x)^2 \in \mathbb{P}$ and one of $(x+2)^2+(n-x)^2$,
   $(x+1)^2+(n-x+1)^2$, $x^2+(n-x+2)^2$ is in $\mathbb{P}.$


Weaker version : Any odd number is of the form $a+b$ where $a^2+b^2$ is prime
Stronger version : Yet an other conjecture about odd numbers $n=a+b$ such that $a^2+b^2$ is prime
Both of the above problems are questions posted by OP. This conjecture will remain unsolved unless the Weaker version is solved. As defined in the Weaker version, we can find a rough estimate for $k(n)$ and then define the following:
Let $f : \mathbb{N} \to \mathbb{N}$ be a function and $x \in \mathbb{N}$. We choose $f(x)$ values from $\{1,2,...,x\}$ and add them to the set $A$, and $f(x+2)$ values from $\{1,2,...,x+2\}$, adding them to the set $B$. Let $P(f,x)$ be the probability that $\exists$ $a \in A$ and $b \in B$ such that $b \in \{a,a+1,a+2\}$.
We can then heuristically find a $g \sim k$ and if: 
$$\lim_{x\to \infty}P(g,x) \to 1$$
then it adds evidence to the conjecture to be true. However, if $g$ grows sufficiently slower than a linear function, then this be untrue.
