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](http://en.wikipedia.org/wiki/Sophie_Germain_Prime)*
(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.



Why are this operator's primes the Sophie Germain primes?
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$.


