Is it true that $8k+3=x^2+y^2+p^2,\forall k\in \mathbb N$? Is it true that for every $k\in \mathbb N,$ we can find $x,y\in \mathbb Z$ and $p=1$ or $p\in P $ such that $$8k+3=x^2+y^2+p^2$$? I checked this for all $k\leq 10^5,$ but cannot prove it.
Thanks in advance!
 A: This conjecture is closely related to polygonal number theorem (triangular case):

every positive integer is a sum of $3$ triangular numbers:
$$\forall k \in \mathbb{N}:\qquad k=x+y+z,\qquad x,y,z\in T\tag{1},$$
  where $T$ is the set of triangular numbers: $T = \{0,1,3,6,10,15,21,28,36,45,55,66,78,91,105,120,136,153,171,...\}$.

(See also  Gaussian  "Eureka theorem", 1796).
It is easy to see, that $a,b,p$ must be odd numbers.
Denote $a=2\alpha+1$, $b=2\beta+1$, $p = 2\gamma+1$, where $\alpha,\beta,\gamma\in \mathbb{Z}_+$.
Then 
$$8k = 4\alpha(\alpha+1)+4\beta(\beta+1)+4\gamma(\gamma+1),$$
$$k = \frac{\alpha(\alpha+1)}{2} + \frac{\beta(\beta+1)}{2} + \frac{\gamma(\gamma+1)}{2},$$
then your statement is equivalent to:
$$\forall k\in\mathbb{N}:\qquad k=x+y+z,~~~~~~~x,y\in T, \;\; z\in M\subset T,\tag{2}$$
where $M$ is the set of triangular numbers, that have pattern $z=\frac{(p-1)(p+1)}{8}$, where $p=1$ or $p\in \mathbb{P}$.

$M = \{0,1,3,6,\quad 15,21,\quad 36,45,\quad 66,\quad \quad 105,120, \quad \quad 171, ...\}$.

Your statement is more strong than Eureka theorem. Perhaps it is true. 

I checked all $k\le 5\times 10^8$. There are no counterexamples here.
Algorithm was:


*

*Create an array $m[N]$ of "flags"($0$/$1$); that means:
if $m[k]$ is $0$, then $(2)$ is impossible for this $k$, if $m[k]$ is $1$, then $(2)$ is possible for this $k$;

*set all values of this array to zero initially: $m[k]=0$; 

*$\forall z\in M$ to set $m[z]=1$;

*for each $m[k]$ which is $1$,  to set $m[k+t]=1$, where $t\in T$;

*(again) for each $m[k]$ which is $1$,  to set $m[k+t]=1$, where $t\in T$.


After that we'll check if there exist some $m[k]=0$.
Algorithm parameters: 
 - memory used: $O(N)$, 
 - time: $O(N^{3/2})$.
A: This is apparently a hard problem. Duke, Friedlander, and Iwaniec showed in their Int. Math. Res. Notices paper "Weyl sums for quadratic roots" that this is true for all sufficiently large $k$, but they had to assume two big conjectures in analytic number theory (GRH and Elliott-Halberstam). See Theorem 1.6, although there it's stated for different congruence conditions than the $N\equiv3\pmod 8$ you're interested in.
