the sum of two arbitrary different numbers in the sequence is always coprime with the sum of three arbitrary...











up vote
11
down vote

favorite
5













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 ?










share|cite|improve this question




















  • 3




    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.
    – Gerry Myerson
    Nov 13 at 1:30






  • 4




    What's the source of this question, please?
    – Gerry Myerson
    Nov 13 at 9:58






  • 1




    @Empy2, a sequence of length 4 that works is 23, 179, 399, 1271.
    – Mees de Vries
    Nov 13 at 11:31






  • 1




    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.
    – Mees de Vries
    Nov 13 at 11:32








  • 1




    Let me amplify @GerryMyerson's question: where did you encounter this problem? Did you think it up yourself?
    – John Hughes
    Nov 13 at 13:06















up vote
11
down vote

favorite
5













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 ?










share|cite|improve this question




















  • 3




    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.
    – Gerry Myerson
    Nov 13 at 1:30






  • 4




    What's the source of this question, please?
    – Gerry Myerson
    Nov 13 at 9:58






  • 1




    @Empy2, a sequence of length 4 that works is 23, 179, 399, 1271.
    – Mees de Vries
    Nov 13 at 11:31






  • 1




    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.
    – Mees de Vries
    Nov 13 at 11:32








  • 1




    Let me amplify @GerryMyerson's question: where did you encounter this problem? Did you think it up yourself?
    – John Hughes
    Nov 13 at 13:06













up vote
11
down vote

favorite
5









up vote
11
down vote

favorite
5






5






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 ?










share|cite|improve this question
















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 ?







calculus combinatorics number-theory elementary-number-theory






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Nov 13 at 12:30

























asked Nov 13 at 1:27









apple

1




1








  • 3




    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.
    – Gerry Myerson
    Nov 13 at 1:30






  • 4




    What's the source of this question, please?
    – Gerry Myerson
    Nov 13 at 9:58






  • 1




    @Empy2, a sequence of length 4 that works is 23, 179, 399, 1271.
    – Mees de Vries
    Nov 13 at 11:31






  • 1




    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.
    – Mees de Vries
    Nov 13 at 11:32








  • 1




    Let me amplify @GerryMyerson's question: where did you encounter this problem? Did you think it up yourself?
    – John Hughes
    Nov 13 at 13:06














  • 3




    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.
    – Gerry Myerson
    Nov 13 at 1:30






  • 4




    What's the source of this question, please?
    – Gerry Myerson
    Nov 13 at 9:58






  • 1




    @Empy2, a sequence of length 4 that works is 23, 179, 399, 1271.
    – Mees de Vries
    Nov 13 at 11:31






  • 1




    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.
    – Mees de Vries
    Nov 13 at 11:32








  • 1




    Let me amplify @GerryMyerson's question: where did you encounter this problem? Did you think it up yourself?
    – John Hughes
    Nov 13 at 13:06








3




3




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.
– Gerry Myerson
Nov 13 at 1:30




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.
– Gerry Myerson
Nov 13 at 1:30




4




4




What's the source of this question, please?
– Gerry Myerson
Nov 13 at 9:58




What's the source of this question, please?
– Gerry Myerson
Nov 13 at 9:58




1




1




@Empy2, a sequence of length 4 that works is 23, 179, 399, 1271.
– Mees de Vries
Nov 13 at 11:31




@Empy2, a sequence of length 4 that works is 23, 179, 399, 1271.
– Mees de Vries
Nov 13 at 11:31




1




1




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.
– Mees de Vries
Nov 13 at 11:32






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.
– Mees de Vries
Nov 13 at 11:32






1




1




Let me amplify @GerryMyerson's question: where did you encounter this problem? Did you think it up yourself?
– John Hughes
Nov 13 at 13:06




Let me amplify @GerryMyerson's question: where did you encounter this problem? Did you think it up yourself?
– John Hughes
Nov 13 at 13:06










2 Answers
2






active

oldest

votes

















up vote
2
down vote



accepted










For the record:



https://artofproblemsolving.com/community/c6h1441130p8200462



All Russian Math Olympiad...



enter image description here






share|cite|improve this answer




























    up vote
    2
    down vote













    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,bin 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$, $kinmathbb Z$. Thus, from the set of "currently available for picking" numbers, we want to remove the set ${kp-b:kinmathbb 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.






    share|cite|improve this answer























    • Nice try, fell short but you did your best. So +1.
      – Oldboy
      Nov 13 at 19:10










    • @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 :)
      – Mirko
      Nov 13 at 19:19










    • @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. $6kpm 1$ are twin primes iff $kne 6ijpm 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.
      – Keith Backman
      Nov 13 at 19:57










    • @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
      – Mirko
      2 days ago











    Your Answer





    StackExchange.ifUsing("editor", function () {
    return StackExchange.using("mathjaxEditing", function () {
    StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
    StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
    });
    });
    }, "mathjax-editing");

    StackExchange.ready(function() {
    var channelOptions = {
    tags: "".split(" "),
    id: "69"
    };
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function() {
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled) {
    StackExchange.using("snippets", function() {
    createEditor();
    });
    }
    else {
    createEditor();
    }
    });

    function createEditor() {
    StackExchange.prepareEditor({
    heartbeatType: 'answer',
    convertImagesToLinks: true,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: 10,
    bindNavPrevention: true,
    postfix: "",
    imageUploader: {
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    },
    noCode: true, onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    });


    }
    });














     

    draft saved


    draft discarded


















    StackExchange.ready(
    function () {
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2996157%2fthe-sum-of-two-arbitrary-different-numbers-in-the-sequence-is-always-coprime-wit%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown

























    2 Answers
    2






    active

    oldest

    votes








    2 Answers
    2






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes








    up vote
    2
    down vote



    accepted










    For the record:



    https://artofproblemsolving.com/community/c6h1441130p8200462



    All Russian Math Olympiad...



    enter image description here






    share|cite|improve this answer

























      up vote
      2
      down vote



      accepted










      For the record:



      https://artofproblemsolving.com/community/c6h1441130p8200462



      All Russian Math Olympiad...



      enter image description here






      share|cite|improve this answer























        up vote
        2
        down vote



        accepted







        up vote
        2
        down vote



        accepted






        For the record:



        https://artofproblemsolving.com/community/c6h1441130p8200462



        All Russian Math Olympiad...



        enter image description here






        share|cite|improve this answer












        For the record:



        https://artofproblemsolving.com/community/c6h1441130p8200462



        All Russian Math Olympiad...



        enter image description here







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered yesterday









        Oldboy

        5,4031527




        5,4031527






















            up vote
            2
            down vote













            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,bin 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$, $kinmathbb Z$. Thus, from the set of "currently available for picking" numbers, we want to remove the set ${kp-b:kinmathbb 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.






            share|cite|improve this answer























            • Nice try, fell short but you did your best. So +1.
              – Oldboy
              Nov 13 at 19:10










            • @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 :)
              – Mirko
              Nov 13 at 19:19










            • @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. $6kpm 1$ are twin primes iff $kne 6ijpm 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.
              – Keith Backman
              Nov 13 at 19:57










            • @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
              – Mirko
              2 days ago















            up vote
            2
            down vote













            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,bin 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$, $kinmathbb Z$. Thus, from the set of "currently available for picking" numbers, we want to remove the set ${kp-b:kinmathbb 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.






            share|cite|improve this answer























            • Nice try, fell short but you did your best. So +1.
              – Oldboy
              Nov 13 at 19:10










            • @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 :)
              – Mirko
              Nov 13 at 19:19










            • @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. $6kpm 1$ are twin primes iff $kne 6ijpm 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.
              – Keith Backman
              Nov 13 at 19:57










            • @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
              – Mirko
              2 days ago













            up vote
            2
            down vote










            up vote
            2
            down vote









            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,bin 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$, $kinmathbb Z$. Thus, from the set of "currently available for picking" numbers, we want to remove the set ${kp-b:kinmathbb 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.






            share|cite|improve this answer














            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,bin 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$, $kinmathbb Z$. Thus, from the set of "currently available for picking" numbers, we want to remove the set ${kp-b:kinmathbb 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.







            share|cite|improve this answer














            share|cite|improve this answer



            share|cite|improve this answer








            edited Nov 13 at 16:39

























            answered Nov 13 at 14:26









            Mirko

            7,728930




            7,728930












            • Nice try, fell short but you did your best. So +1.
              – Oldboy
              Nov 13 at 19:10










            • @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 :)
              – Mirko
              Nov 13 at 19:19










            • @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. $6kpm 1$ are twin primes iff $kne 6ijpm 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.
              – Keith Backman
              Nov 13 at 19:57










            • @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
              – Mirko
              2 days ago


















            • Nice try, fell short but you did your best. So +1.
              – Oldboy
              Nov 13 at 19:10










            • @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 :)
              – Mirko
              Nov 13 at 19:19










            • @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. $6kpm 1$ are twin primes iff $kne 6ijpm 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.
              – Keith Backman
              Nov 13 at 19:57










            • @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
              – Mirko
              2 days ago
















            Nice try, fell short but you did your best. So +1.
            – Oldboy
            Nov 13 at 19:10




            Nice try, fell short but you did your best. So +1.
            – Oldboy
            Nov 13 at 19:10












            @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 :)
            – Mirko
            Nov 13 at 19:19




            @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 :)
            – Mirko
            Nov 13 at 19:19












            @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. $6kpm 1$ are twin primes iff $kne 6ijpm 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.
            – Keith Backman
            Nov 13 at 19:57




            @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. $6kpm 1$ are twin primes iff $kne 6ijpm 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.
            – Keith Backman
            Nov 13 at 19:57












            @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
            – Mirko
            2 days ago




            @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
            – Mirko
            2 days ago


















             

            draft saved


            draft discarded



















































             


            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2996157%2fthe-sum-of-two-arbitrary-different-numbers-in-the-sequence-is-always-coprime-wit%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown







            Popular posts from this blog

            Актюбинская область

            QoS: MAC-Priority for clients behind a repeater

            AnyDesk - Fatal Program Failure