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 ?
  • 1
    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
up vote 7 down vote accepted

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:

Number of representations as pq+rs with p, q, r, s all 3-digit primes

Number of representations as pq+rs with p, q, r, s all 4-digit primes

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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.