Question

If we ask which natural numbers n are not expressible as n = ab + bc + cd (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 <= b <= 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 >= 1 and b,c >= 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.

Answer 1

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://www.research.att.com/~njas/sequences/A000926

Chowla showed that the list is finite and Weinberger showed that there is at most one further term.

Answer 2

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.

Answer 3

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+n² 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)² - n² will be bigger than p.

Answer 4

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://www.research.att.com/~njas/sequences/A000926