# Special representation of a number

How can I check, if a number $n$ can be representated by

$$pq+rs$$

where $p,q,r,s$ are pairwise different prime numbers with the same number of digits.

For example,

$$105153899965560312960 = 3022993637\times 6003631993 + 9069920719\times 9592692301$$

has such a representation.

My questions :

• Is such a representation (if it exists), always unique ?
• How can I find the primes $p,q,r,s$ if a representation exists ?
• How can I check if a representation exists ?
• There is a very large number of counterexamples to your uniqueness conjecture, of which the smallest is $$11\cdot13 + 19\cdot 29 = 11\cdot 43 + 13\cdot 17$$ – MJD May 20 '15 at 13:12
• So, the first part is answered. Thank you. And I conjectured the uniqueness only for numbers large enough. It would be interesting, which is the largest counterexample (I think there is a largest). – Peter May 20 '15 at 13:14

You said in a comment:

I conjectured the uniqueness only for numbers large enough. It would be interesting, which is the largest counterexample (I think there is a largest).

I think your intuition is backwards here, and I think it will be instructive if I explain to you why; this is also why I was able to immediately guess that there would be counterexamples. Short summary: There so many 4-tuples compared with the number of possible sums that it is not possible for every 4-tuple to get its own sum.

Suppose our primes have $d$ digits and that there are $D$ primes with $d$ digits. The prime number theorem tells us that $D$ is around $O\left(\frac{10^d}{d}\right)$.

Then there are $O(D^4) = O\left(\frac{10^{4d}}{d^4}\right)$ quadruples $(p,q,r,s)$ of distinct $d$-digit primes. The quantity $n=pq+rs$ has around $2d$ digits and there are $10^{2d}$ of these numbers.

There is no reason to think that the quantities $pq+rs$ will be distributed among these $10^{2d}$ possibilities in any way other than randomly. (Additive properties of prime numbers are almost always random unless there is some obvious reason they cannot be. To take an example I made up on the spot, the mod-3 remainder of $p+q$ is equal to 0, 1, or 2 with probability close to $\frac12, \frac14, \frac14$ just as one would expect.)

So we should expect that what we are doing here is essentially throwing $O\left(\frac{10^{4d}}{d^4}\right)$ balls at random into only $10^{2d}$ bins . The number of balls greatly exceeds the number of bins when $d$ is large, so it is not at all surprising that some balls end up in the same bin; that is, that some tuples yield the same value for $pq+rs$. As $d$ increases, we should expect this to be vastly more likely, not less likely, and this argues strongly against the possibility of a maximal counterexample.

Indeed, one would expect the opposite to be true: let $N$ be given. Then we should expect to find many sets, each containing $N$ 4-tuples, for which all the 4-tuples in the set have the same $pq+rs$ value, no matter how large $N$ is large. If we want to find $n$ that can be represented as $n=pq+rs$ in one million different ways, we should expect that there will be many such.

(The tuples won't be distributed uniformly over the space of sums—for example, only a few tuples map to an odd sum—but this will tend to increase, not decrease, the number of collisions.)

• That is convincing. +1 for the well explanation. – Peter May 20 '15 at 13:37
• Experiments bear out this theory. There are 20 ways to represent 3150 in the form $n=pq+rs$, and this is the most ways for any $n$ under 10,000. But if we start looking at larger primes, there are over ten thousand such $n$ below 200,000; for example there are 20 or more ways to represent each of 170280, 170430, 170436, 170520, 170790, 170940, 170970, 171318, 171780, 171990, 172410… – MJD May 20 '15 at 13:49

(Just to elaborate on MJD's answer.)

Note that if $p, q, r, s$ are all $d$ digits long, which means that they all lie in the interval $[10^{d-1}, 10^d)$, then $pq + rs$ lies in the interval $[2\times10^{2d-2}, 2\times10^d)$. For numbers $N$ that lie close to the endpoints of this interval there will be few representations as $pq + rs$, while for numbers "well inside" this interval there ought to be many.

Let's dispose of the case of $1$-digit primes: in that case $\{p, q, r, s\} = \{2, 3, 5, 7\}$, and the only possible values of $pq + rs$ are $\{29, 31, 41\}$. For larger lengths, $p, q, r, s$ are all odd numbers, so $pq + rs$ is even.

I computed the number of representations as $pq + rs$ for $p, q, r, s$ being 3-digit and 4-digit primes, respectively. For 3-digit primes numbers with such a representation lie in the interval $[20000, 2000000]$ (actually $[22030,1948418]$), and for 4-digit primes they lie in the interval $[2000000, 200000000]$ (actually $[2062436,198303900]$). Plotting them gives:

Far from the representation as $pq+rs$ being unique,

• all even numbers in $[60198, 1217132]$ have at least $2$ representations,

• all even numbers in $[90376, 1038516]$ and in $[3667846, 161023932]$ have at least $10$ representations,

• all even numbers in $[12346780, 95078484]$ have at least $1000$ representations, etc.

There are even numbers with over $12000$ representations as you can see, and as you go to larger $N$ this will only increase.

I think there is nothing special about prime numbers here (once you start adding them): if you take merely "odd numbers" you'd probably see something similar.

• The remarkable resemblance of the two plots is interesting though, and I'm curious what the general shape (of the "upper" and "lower" curves) are. – ShreevatsaR Jun 28 '15 at 16:33