Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

4 Answers 4

up vote 6 down vote accepted

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.

share|improve this answer
    
Very nice! Looking at the list of known examples, only 2,3,5,7,13 and 37 are prime. So there is at most one more prime we don't know about. –  David Speyer Nov 21 '09 at 21:24

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.

share|improve this answer
    
I looked at the wikipedia entry for Sophie Germain prime and it stated it as a prime p where 2p+1 is prime. Your argument still works though p must not be 2q+1 where q is a Sophie Germain prime or it must not be the matching safe prime of a Sophie Germain prime. –  Kristal Cantwell Nov 21 '09 at 20:36
    
If a Sophie Germain prime p is of the form 2q+1 where q is prime then p+1/2-1 is prime so it looks like it will make a difference. Look at 37 37+1 = 38 =2*19 and your agument breaks down but 37 is not a Sophie Germain prime or a matching safe prime because it is equal to 1 mod 6 not 5 mod six. I think your argument works for everything except p and 2p-1 paris which is different from p, 2p+1 of the Sophie Germain prime –  Kristal Cantwell Nov 21 '09 at 21:08

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.

share|improve this answer

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

share|improve this answer
    
The argument is just to choose an $a$ and a $b$, in particular, $1$ and $2$, and then the problem reduces to "Which primes can be written as $2n+3$ for some $n\geq 2$. That's the same as $(2n+2)+1=2k+1$ for $k\geq 3$, so every odd number greater than seven, and in particular, every odd prime, can be written this way. –  Charles Siegel Nov 21 '09 at 18:47
2  
You get 3n +2, not 2n+3. –  Gian Maria Dall'Ara Nov 21 '09 at 18:50
    
You are right I corrected this –  Kristal Cantwell Nov 21 '09 at 19:33
    
I am not sure why is your argument correct. Can you find a representation for say 37? The only representation I find is 37 = 1*18 + 18 + 1 –  Jernej Nov 21 '09 at 20:05
    
37 is not of the form 3n+2 and your representation doesn't satisfy the strictly increasing condition. –  Qiaochu Yuan Nov 21 '09 at 20:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.