# Compressing the primes using simple addition?

Consider the sets of integers $$A = \{1, 3, 7, 13, 27\} \\ B = \{4, 10, 16, 40, 100\}$$

Elementwise addition of sets $$A, B$$ looks like $$A + B := \{ a + b: a \in A, b \in B\}$$.

Now elementwise-add them to form $$A + B$$. Here is the result: $$\begin{matrix} + & 1 & 3 & 7 & 13 & 27 & \\ 4 & 5 & 7 & 11 & 17 & 31 & \\ 10 & 11 & 13 & 17 & 23 & 37 \\ 16 & 17 & 19 & 23 & 29 & 43 \\ 40 & 41 & 43 & 47 & 53 & 67 \\ 100 & 101 & 103 & 107 & 113 & 127\\ \end{matrix}$$

As you can see, this doesn't perfectly list the first $$n$$ primes since $$59$$ is missing.

Can you come up with two sets of integers $$A, B$$ such that $$A + B$$ consists only of prime numbers and such that $$|A + B| \gt 20$$. In other words, can you beat me in my example above?

Thus, if we don't examine the size of the integers involved in the above matrix, we've effectly compressed $$n^2 - n$$ primes into $$2n$$ numbers where $$n = 5$$. I don't know about you, but to me that seems pretty darn interesting!

Continuing from above (by pen & paper): $$\begin{matrix} + & 1 & 3 & 7 & 13 & 27 & 57 &\\ 4 & 5 & 7 & 11 & 17 & 31 & 61\\ 10 & 11 & 13 & 17 & 23 & 37 & 67\\ 16 & 17 & 19 & 23 & 29 & 43 & 73\\ 40 & 41 & 43 & 47 & 53 & 67 & 97\\ 100 & 101 & 103 & 107 & 113 & 127 & 157\\ \end{matrix}$$

Here's a script you can play with:

from sympy.ntheory import prime, isprime

# Seed with whatever you want:
A = [1, 3, 7]
B = [4, 10, 16]

M = 1000

for k in range(0, M):
if k % 2 == 0:
b = max(B) + 1
for n in range(b, b + M):
for a in A:
if not isprime(a + n):
break
else:
B.append(n)
break
else:
a = max(A) + 1
for n in range(a, a + M):
for b in B:
if not isprime(b + n):
break
else:
A.append(n)
break

C = set()
for a in A:
for b in B:
return list(C)

print(A)
print(B)
C.sort()
print(C)


## Outputs:

[1, 3, 7, 13, 27, 63, 97]
[4, 10, 16, 40, 100, 346, 1090, 1426]
[5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 67, 73, 79, 101, 103, 107, 113, 127, 137, 163, 197, 347, 349, 353, 359, 373, 409, 443, 1091, 1093, 1097, 1103, 1117, 1153, 1187, 1427, 1429, 1433, 1439, 1453, 1489, 1523]


Did some thought on the problem:

Ease the constraints some, and allow $$0, \pm 1$$ into the result set of $$A + B$$.

Take a finite subsquare of the composition group law for $$(\Bbb{Z}, +)$$. For example:

$$\begin{matrix} -2 & (-1) & 0 & 1 & 2 & (3) & 4 & (5) \\ -1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & \\ 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\ 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\\ 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ 6 & (7) & 8 & 9 & 10 & (11) & 12 & (13) \\ \vdots \\ 12 & (13) & 14 & 15 & 16 & (17) & 18 & (19) \\ \end{matrix}$$

First, assume that $$7$$ is in $$A$$ and highlight the prime columns with parentheses like above. Those are the only columns that you can select from to fill out $$B$$. Since we don't want to delete anything from $$A$$, highlight all rows such that the rows prime columns contain row "7"s prime columns. This is done in the table above.

• Do you mean $|A| \cdot |B| >25$? (your example achieves product $25$ but sum only $10$) – coffeemath Oct 20 '18 at 7:44
• @coffeemath you're right, that's what I mean. Such that $|A + B| \gt 20$ (I counted them up!) – BananaCats Category Theory App Oct 20 '18 at 7:46
• Are we looking to list the first $K$ consecutive primes? Or you only care about listing some primes, regardless of their consecutivity? – RGS Oct 20 '18 at 9:53
• You can have A as {$1$} and B as {$p_1-1, p_2-1 \cdot\cdot\cdot p_{26}-1$} where $p_x$ is a prime, to suit your conditions. But that’s not what you’re looking for. So both sets should have absolute size of at least $2$. – Kyky Oct 20 '18 at 12:15
• Perhaps, to make this more interesting, you should require that $A$ and $B$ have the same number of elements? – TonyK Oct 20 '18 at 14:12

Here is an example if we are only requiring $$A+B$$ consist of primes (and not the first $$n$$ primes).

Let $$Q_n=\{a_1,\ldots, a_n\}$$ be a set of prime numbers such that $$a_i \equiv 1 \pmod {10}$$ and $$a_{i}+2$$ is also a prime. Using a twin prime table, this is easy to obtain. For example, we can let $$Q_{10}=\{11, 71, 101, 191, 281, 311, 431, 461, 821, 881\}.$$ Then let $$A=\{1,3\}$$ and $$B=\{a-1: a \in Q_n\}$$, and $$A+B$$ will consist of exactly 20 primes.

Since there are arbitrarily long arithmetic progressions of primes, theoretically one should be able to make $$A$$ and $$B$$ have any size.

$$|A|=|B|=8,\space |A+B|=64$$

I have spiced it up a little bit, numbers in each row are consecutive primes.

$$\begin{matrix} & 165523 & 165527 & 165533 & 165541 & 165551 & 165553 & 165559 & 165569 \\ \\ +1099560& 1265083 & 1265087 & 1265093 & 1265101 & 1265111 & 1265113 & 1265119 & 1265129 \\ +6067230& 6232753 & 6232757 & 6232763 & 6232771 & 6232781 & 6232783 & 6232789 & 6232799 \\ +16348200& 16513723 & 16513727 & 16513733 & 16513741 & 16513751 & 16513753 & 16513759 & 16513769 \\ +41967240& 42132763 & 42132767 & 42132773 & 42132781 & 42132791 & 42132793 & 42132799 & 42132809 \\ +56322420& 56487943 & 56487947 & 56487953 & 56487961 & 56487971 & 56487973 & 56487979 & 56487989 \\ +65835840& 66001363 & 66001367 & 66001373 & 66001381 & 66001391 & 66001393 & 66001399 & 66001409 \\ +92498820& 92664343 & 92664347 & 92664353 & 92664361 & 92664371 & 92664373 & 92664379 & 92664389 \\ +95634000& 95799523 & 95799527 & 95799533 & 95799541 & 95799551 & 95799553 & 95799559 & 95799569 \end{matrix}$$

• How did you generate this, and why did you use such big numbers? – BananaCats Category Theory App Oct 20 '18 at 20:56
• @EnjoysMath Obviously with computer, I can post the code here if you want to play with it. This is the smallest matrix that has 9 rows made of 8 consecutive prime numbers with each row having the same prime gaps as the first one. It’s pretty amazing that all increments in the first column are divisible by 10. – Oldboy Oct 20 '18 at 21:45
• Yes, pleaes post the code. – BananaCats Category Theory App Oct 20 '18 at 22:18