8
$\begingroup$

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


def elementwise_add(A, B):
    C = set()
    for a in A:
        for b in B:
            C.add(a + b)
    return list(C)

print(A)
print(B)
C = elementwise_add(A, 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.

$\endgroup$
  • 1
    $\begingroup$ Do you mean $|A| \cdot |B| >25$? (your example achieves product $25$ but sum only $10$) $\endgroup$ – coffeemath Oct 20 '18 at 7:44
  • $\begingroup$ @coffeemath you're right, that's what I mean. Such that $|A + B| \gt 20$ (I counted them up!) $\endgroup$ – BananaCats Category Theory App Oct 20 '18 at 7:46
  • 2
    $\begingroup$ Are we looking to list the first $K$ consecutive primes? Or you only care about listing some primes, regardless of their consecutivity? $\endgroup$ – RGS Oct 20 '18 at 9:53
  • 1
    $\begingroup$ 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$. $\endgroup$ – Kyky Oct 20 '18 at 12:15
  • 1
    $\begingroup$ Perhaps, to make this more interesting, you should require that $A$ and $B$ have the same number of elements? $\endgroup$ – TonyK Oct 20 '18 at 14:12
1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ How did you generate this, and why did you use such big numbers? $\endgroup$ – BananaCats Category Theory App Oct 20 '18 at 20:56
  • $\begingroup$ @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. $\endgroup$ – Oldboy Oct 20 '18 at 21:45
  • $\begingroup$ Yes, pleaes post the code. $\endgroup$ – BananaCats Category Theory App Oct 20 '18 at 22:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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