11
$\begingroup$

Does there exist a sequence of infinite positive integers $a_1,a_2,...$ such that the sum of two arbitrary different numbers in the sequence is always coprime with the sum of three arbitrary different numbers in the sequence?

Assume that there exist such sequence.

For every prime $p$, if there exist three numbers from the sequence $a_i,a_j,a_k$ that are divisible by $p$, then $a_i+a_j$ is not coprime with $a_i+a_j+a_k$, contradiction. Thus $p$ can divide at most two numbers from the sequence. Therefore there are at most two even numbers from the sequence and there are infinite odd numbers from that sequence.

However, if there are two even numbers, then the sum of two odd numbers is not coprime with the sum of two odd numbers and an even one, since both of the sum are greater than $2$ and are both even. Hence there are no even numbers in the sequence.

Here I am stuck. How can I progress ? Is there a better way to solve the problem ?

$\endgroup$
  • 3
    $\begingroup$ If there's one even number, $a$, then $a+b+c$ won't be coprime to $b+c$, so it seems to me there can't be any even numbers. $\endgroup$ – Gerry Myerson Nov 13 '18 at 1:30
  • 4
    $\begingroup$ What's the source of this question, please? $\endgroup$ – Gerry Myerson Nov 13 '18 at 9:58
  • 1
    $\begingroup$ @Empy2, a sequence of length 4 that works is 23, 179, 399, 1271. $\endgroup$ – Mees de Vries Nov 13 '18 at 11:31
  • 1
    $\begingroup$ And for length 5 we have, for example, [7649, 13109, 2831, 449, 13469]. Edit: and for length 6, we can take [240121741557, 433676463451, 640018399849, 14872633681, 693923146771, 606492629611]. These examples are just generated by trying short lists of random distinct odd numbers in a large range. $\endgroup$ – Mees de Vries Nov 13 '18 at 11:32
  • 1
    $\begingroup$ Let me amplify @GerryMyerson's question: where did you encounter this problem? Did you think it up yourself? $\endgroup$ – John Hughes Nov 13 '18 at 13:06
2
$\begingroup$

For the record:

https://artofproblemsolving.com/community/c6h1441130p8200462

All Russian Math Olympiad...

enter image description here

$\endgroup$
2
$\begingroup$

This is an extended comment and not a complete answer. It describes an idea which to me seems obviously relevant, and which I did not pursue in detail.

We could (attempt to) build such a sequence inductively, adding one integer at a time. That is we could start with $P_2=\{a_1,a_2\}$ and find a suitable $a_3$ to form $P_3=\{a_1,a_2,a_3\}$ that "works so far". In general, if $P_n=\{a_1,a_2,...,a_n\}$, find and add a suitable $a_{n+1}$ that makes $P_{n+1}=\{a_1,a_2,...,a_n,a_{n+1}\}$ work.

I tend to think of the $P_n$ consisting of prime numbers (though that perhaps need not be a requirement).

What are some conditions, restrictions in picking $a_{n+1}$? If $P_n$ has been defined, we could look at all pairs $(a,b)$ of elements of $P_n$, look at all prime divisors of $a+b$, and make sure that the new number $c=a_{n+1}$ that we pick is not divisible by any of these $p$. This seems like a requirement that is easy to satisfy, since we are never going to run out of big primes (new big ones, not divisible by the old ones).

Another requirement, which I think is more important, say $c=a_{n+1}$ is the new integer we want to pick and add to $P_n$, to obtain $P_{n+1}$, and say $a,b\in P_n$. For any prime $p$ that divides $a$ we want to make sure that $p$ does not divide $b+c$. (Note there is symmetry here, we may interchange $a$ and $b$.) So we want to rule out all $c$ with $kp=b+c$, $k\in\mathbb Z$. Thus, from the set of "currently available for picking" numbers, we want to remove the set $\{kp-b:k\in\mathbb Z\}$.

Here is an illustration, starting with $P_2=\{3,5\}$. Remove $\{1,4,7,10,13,...\}$, and also remove $\{2,7,12,17,...\}$. (Note we are removing two arithmetic progressions $3k-5$ and $5k-3$.) If (for presumed convenience and to stay out of unforeseen trouble) we stick to pick primes, the prime $7$ has been ruled out, but $11$ is available, so we take $P_3=\{3,5,11\}.$ (Picking primes allows for another simplification of the rule excluding new candidates, I think, but will not try to write it down.)

Now, the pair $(3,5)$ has already been taken care of (that is, we remember that we should never pick numbers $3k-5$ and $5k-3$). The pair $(3,11)$ tells us not to pick numbers $\{8,19,30,41,52,...\}$ or numbers $\{1,4,7,10,13,16,...\}$ (and the latter (co-)set was taken care of, already). The pair $(5,11)$ rules out numbers $\{6,17,28,39,50,...\}$ and $\{4,9,14,19,...\}$. In addition $3+11=14$ with a prime factor of 7, ruling out all multiples of $7$ as well (but this was the "easy" not to worry too much about, part of the ruling out process). It so happens that $3+5$ and $5+11$ are both powers of $2,$ but we have already ruled out even numbers since we read the comments.

The question, of course, could this process, this inductive picking of new numbers, go on forever? If we had included an even number in $P_2$ then the answer is no. What about $P_2=\{3,5\}$ or an even better (in what way) choice of $P_2$? Obviously the problem has something to do with arithmetic progressions, at every step we have excluded finitely many arithmetic progressions, do we reach a step when we covered all integers with finitely many arithmetic progressions? (That is, we ruled out all the integers and there is nothing that remains available to pick a new number from.) I believe this topic is well-researched, and someone could easily complete the solution, hopefully. (That is to say, I do not feel competent to do it myself, and I can't really tell what others could do :) (I tend to think of Hales–Jewett theorem, but didn't think hard enough to see if it is relevant.)

I just realized I was (implicitly) thinking of a restricted version of the problem, saying that if $a,b,c$ are members of the sequence then the sum of any two members of $\{a,b,c\}$ is coprime with $a+b+c$. I didn't think of the case when we pick four or five members of the sequence, say $a,b,c,d,e$, so I didn't think of the requirement (and variations thereof) that $a+b$ is coprime with $c+d+e$. So now I think the problem is more complicated, at least for me, than I had assumed earlier. This, on one hand, makes me feel it would be more difficult to show that such a sequence exists, on the other hand it seems that even for the full version of the problem one could express the set of excluded integers at each stage (i.e. at each inductive step) as the union of finitely many arithmetic progressions.

$\endgroup$
  • $\begingroup$ Nice try, fell short but you did your best. So +1. $\endgroup$ – Oldboy Nov 13 '18 at 19:10
  • $\begingroup$ @Oldboy Thank you! I do find this translation into arithmetic progressions relevant, even if once this translation is done, I do not know what to do with it :) $\endgroup$ – Mirko Nov 13 '18 at 19:19
  • $\begingroup$ @Mirko Can we cover all integers $(>N)$ with finitely many arithmetic progressions? Trivially, yes (e.g. odds and evens). But the question is deeply relevant to the twin prime conjecture. $6k\pm 1$ are twin primes iff $k\ne 6ij\pm i \pm j$. This yields arithmetic progressions such as $5n-1,\ 5n+1,\ 7n-1,\ 7n+1$ etc. which exclude values of $k$. If the progressions cover all integers greater than some $N$, then there will be a largest twin prime; if not, there is no largest twin prime. I would be most grateful to receive from you any relevant thoughts or information you can provide. $\endgroup$ – Keith Backman Nov 13 '18 at 19:57
  • $\begingroup$ @KeithBackman I do not know, though I feel this is what one should look at. I am glad to see you point out a relation to the twin prime conjecture, but I don't feel I know enough to comment. In my answer I throw out $3k-5$ (same as $3k+1$), and hopefully later we never need to throw out $3k+2$. If for each prime $p$ we need to throw out just one class $pk+m_p$ (for just one $m_p$) then there will be enough numbers left to pick from. So I feel it may be possible to carry out the above suggested construction, but I can't really tell yet, nothing more specific or better at this point. Need think $\endgroup$ – Mirko Nov 13 '18 at 21:52

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.