Prime numbers $p$ not of the form $ab + bc + ac$ $(0 < a < b < c )$ (and related questions) If we ask which natural numbers n are not expressible as $n = ab + bc + ca$ ($0 < a < b < c$) then this is a well known open problem. Numbers not expressible in such form are called    Euler's "numerus idoneus" and it is conjectured that they are finite.
If we omit the condition $a < b < c$ and assume $0 < a \leq b \leq c$ then it was proved (assuming Generalized Riemann Hypothesis) that there is only a finite number of such numbers $n$.
I am interested in the problem of expressing a prime number $p$ as $p = ab + ac + bc$ for $a \geq 1$ and $b,c \geq 2$.
Anybody knows if there is some known result related to expressing prime numbers in such form? This would yield (as a corollary) a very beautiful theorem related to spanning trees in graphs.
 A: I can get all primes of the form $3n+2$. let $a=1, b=2$ and $c=n$ we get $1.2+1n+2n=3n+2$. $n$ is greater than than or equal to $2$. You cannot get $2,3$ and $5$ or $7$ as your smallest number is $8$.
 This gives an infinite number of primes due to Dirichlet's theorem on arithmetic progressions. So we get all primes of the form $3n+2$ greater than $8$. 
We can get some primes of the form $3n+1 1,3,4$ gives $1.3 +1.4+3.4=19$.
We can get an infinite family $3,4,3n+1$ gives $3.4+ 9n+3+12n+4 = 21n+19$ all of these are of form $3n+1$ and again by Dirichlet's theorem there are an infinite number of these. From other posts we have the following argument: 
Now if $p$ is greater than $11$,$(p+1)/2$ is composite for any prime $p$,$p+1$ can be factored into $x,y$ both greater than $2$ and if we take $1, x-1,y-1$ we will get $(x-1)+(y-1)+(x-1)(y-1) =p$ Which eliminates all primes except those where $p+1/2$ is prime. I don't think these are Sophie Germaine primes, if they were we would be done as we have all primes of form $6n+5$ greater than $8$ already represented and Sophie Germaine primes are of the form $6n+5$. 
From another the following are not expressible $2,3,5,7,13$ and $37$ and there is at most one more possible prime not expressible from the above it must be of the form $3n+1$ it also must be larger than $100000000$ see the following:
http://oeis.org/A000926 
A: One can get every prime which is NOT a Sophie Germain prime; that is to say, such that (p+1)/2 is not prime. Proof: if (p+1)/2 is not prime, then we can factor p+1 = xy. If p+1 is not prime, we can impose that x and y are greater than 2 and, since p is prime, it is not of the form x^2-1 (except for p=3). So we can take 2 < x < y. 
Then take (a,b,c) = (1,x-1,y-1).
13 and 37 cannot be achieved.
A: Partial answer: Set a=1, so you want to enumerate the primes of the form b+c+bc = (b+1)(c+1)-1.  This covers all primes p such that p+1 is a product of two factors of size at least 3.  The leftovers (almost certainly covered by other values of a for sufficiently large primes) come from Sophie Germain pairs, which are conjectured to be infinite, but rather sparse.
More generally, the counterexamples are exactly those primes p such that for any positive n,  p+n2 is not a product of two numbers strictly larger than n+1.  It suffices to check for n up to p/4, since for larger n, (n+2)2 - n2 will be bigger than p.
A: Looking at the encyclopedia of integer sequnces, I've found that the set of numbers not expressible as ab + bc + ac 0 < a < b < c is finite.
http://oeis.org/A000926
Chowla showed that the list is finite and Weinberger showed that there is at most one further term.
