8
$\begingroup$

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.

Improve this question
$\endgroup$
0

4 Answers 4

Reset to default
10
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – David E Speyer
    Commented Nov 21, 2009 at 21:24
  • 1
    $\begingroup$ If there is one more prime then Riemann Hypothesis is false (Weinberger's list depends on Riemann). $\endgroup$
    – user76479
    Commented Sep 5, 2015 at 13:58
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Kristal Cantwell
    Commented Nov 21, 2009 at 20:36
  • $\begingroup$ 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 $\endgroup$
    – Kristal Cantwell
    Commented Nov 21, 2009 at 21:08
4
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Charles Siegel
    Commented Nov 21, 2009 at 18:47
  • $\begingroup$ 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 $\endgroup$
    – Jernej
    Commented Nov 21, 2009 at 20:05
  • $\begingroup$ 37 is not of the form 3n+2 and your representation doesn't satisfy the strictly increasing condition. $\endgroup$
    – Qiaochu Yuan
    Commented Nov 21, 2009 at 20:07
3
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .