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
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
|
show 13 more comments
up vote
11
down vote
favorite
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
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
|
show 13 more comments
up vote
11
down vote
favorite
up vote
11
down vote
favorite
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
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
calculus combinatorics number-theory elementary-number-theory
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
|
show 13 more comments
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
|
show 13 more comments
2 Answers
2
active
oldest
votes
up vote
2
down vote
accepted
For the record:
https://artofproblemsolving.com/community/c6h1441130p8200462
All Russian Math Olympiad...
add a comment |
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.
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
add a comment |
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...
add a comment |
up vote
2
down vote
accepted
For the record:
https://artofproblemsolving.com/community/c6h1441130p8200462
All Russian Math Olympiad...
add a comment |
up vote
2
down vote
accepted
up vote
2
down vote
accepted
For the record:
https://artofproblemsolving.com/community/c6h1441130p8200462
All Russian Math Olympiad...
For the record:
https://artofproblemsolving.com/community/c6h1441130p8200462
All Russian Math Olympiad...
answered yesterday
Oldboy
5,4031527
5,4031527
add a comment |
add a comment |
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.
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
add a comment |
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.
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
add a comment |
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.
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.
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
add a comment |
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
add a comment |
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
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