# Why are this operator's primes the Sophie Germain primes?

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.

-
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

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$.

-
@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

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.

-