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

I was seeking a binary operator on natural numbers that is intermediate between the sum and the product, and explored this natural candidate:

$$x \star y = \lceil (x y + x + y)/2 \rceil \;.$$

Then I wondered which numbers are prime with respect to $\star$, i.e., only have one factoring. For example, $11 = 1 \star 10$ is prime but $13 = 1 \star 12 = 2 \star 8$ is not. Computing these $\star$-primes, I found they begin:

$$ 2,3,5,11,23,29,41,53,83,89,113,131,173,179,191, \ldots $$

I tried to prove there were an infinite number of $\star$-primes, but then discovered my primes are precisely the Sophie Germain primes (primes $p$ such that $2p+1$ is also prime), and it is unknown if there are an infinite number of them.

Two questions:

Q1. Why are the $\star$-primes as I defined them precisely the Sophie Germain primes?

I see that factoring $xy + x + y$ to $(x+1)(y+1)-1$ reveals the connection, but my argument for iff is not precise. (Incidentally, the ceiling cannot be ignored: replacing ceiling by floor results in different "primes.")

Q2. Is it possible to express the number of $\star$-divisors of $n$ in terms of a mixture of the number of divisors $\tau(n)$ and the number of partitions $p(n)$?

For example, here are the factors of $n=40$: $$(1 \star 39), (2 \star 26), (3 \star 19), (4 \star 15), (7 \star 9), (8 \star 8) \;,$$ And so 40 has 11 $\star$-divisors: $1, 2, 3, 4, 7, 8, 9, 15, 19, 26, 39 \;.$

I label this recreational because I'm sure this is like eating candy for many of you! Enjoy the snack!

Addendum. Incidentally, if $\star$ is defined using floor rather than ceiling, then the $\lfloor \star \rfloor$-primes $>3$ are even numbers $n$ such that $n+1$ and $2n+1$ are (conventionally) prime. I don't know if these primes have been named, or if it is known whether there are an infinite supply.

share|improve this question
Neat question (even if the solution was mostly elementary)! –  Cam McLeman Dec 8 '10 at 17:24
@Cam: Thanks! :-) –  Joseph O'Rourke Dec 8 '10 at 17:54
Concerning the addendum; so $n+1=p$ is a prime such that $2p-1$ is prime. It is widely believed, but not proved, that there is an infinite supply of such primes. They probably do have a name, which can probably be retrieved by typing the first few into the Online Encyclopedia of Integer Sequences. –  Gerry Myerson Dec 9 '10 at 0:10
@Gerry: Thanks! Indeed they are oeis.org/A123998 . A123998, "Numbers n such that 2n+1 and 4n+1 are primes." Apparently unnamed. But not unstudied! –  Joseph O'Rourke Dec 9 '10 at 0:40
Just came across this discussion from a link back by a more recent question and noticed that no one seems to know the name. Primes $p$ such that $2p-1$ is also prime are often referred to as Cunningham Chains of the First Kind of length 2 (kind of a mouthful). Sophie Germain primes are length 2 CCs of the second kind. –  ARupinski Oct 25 '11 at 22:51

2 Answers 2

up vote 14 down vote accepted

Q1. $p$ is $\star$-prime iff equation $xy+x+y=2p$ has no solution and $xy+x+y=2p-1$ has exactly one solution, i.e. $(x+1)(y+1)=2p+1$ has no solution (which is iff $2p+1$ is prime) and $(x+1)(y+1)=2p$ has only one solution $\{x,y\}=\{1,p-1\}$. This last holds iff $p$ is prime.

Q2. Why partitions?! The number of $\star$-divisors of $n$ equals $\tau(2n+1)+\tau(2n)-4$.

share|improve this answer
@Fedor: Brilliant! But perhaps we are using different conventions for $\tau$: $\tau(79)=2$, $\tau(80)=10$, but this doesn't yield 10 $\star$-divisors for 40... –  Joseph O'Rourke Dec 8 '10 at 13:54
Very nice solution. I fixed a typo. –  Tony Huynh Dec 8 '10 at 14:07
The formula should be $\tau(2n) + \tau(2n+1) - 4$ using your conventions. This gives 11, which seems correct, since you missed the divisor 39. –  ndkrempel Dec 8 '10 at 14:09
@ndk: Thanks, Nick! Your corrections to the formula and to my counting resolve the confusion. –  Joseph O'Rourke Dec 8 '10 at 14:22

In answer to your first question:

As you hinted at, it simplifies things to make the change of variable $x \mapsto x+1$.

Then the product becomes $x \star y = \lceil\frac{xy+1}{2}\rceil$. And we want to find $z$ that can't be expresed as $x \star y$ where $x,y > 2$.

Well that's equivalent to $z$ such that you can't solve $2z=xy+1$ with $x,y>2$, and also you can't solve $2z-1=xy+1$ with $x,y>2$.

The first condition is equivalent to $2z-1$ being prime, since the oddness of $2z-1$ makes the constraint on $x$ and $y$ irrelevant.

The second condition is equivalent to $z-1$ being prime, since it's saying that $2z-2=2(z-1)$ has no non-trivial factorizations beyond the obvious two involving the factor $2$.

Hence overall, we see that $z$ prime in the new sense $\Leftrightarrow$ $z-1$ Sophie Germain prime. Changing variables back, we get the answer to the original question.

share|improve this answer

Your Answer


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.