Arranging numbers on a cycle such that each pair differ by one prime factor? [closed]
$begingroup$
Is it possible to place 2019 natural numbers along a circumference so that, for any two of these numbers, the proportion of the largest to the least is a prime number?
Ok, what I am clear about this problem is that for the ratio to be a number first, it means that given any two numbers, its mcd can not be 1, because in this way we make sure that at least the proportion is a natural number ... However, I am not very clear on how to interpret the part in which it says that they are located along a circumference, that is, How different is it if we place it on a straight?
number-theory
edited Jan 11 at 8:49
Yuval Filmus
48.7k472145
asked Jan 11 at 6:39
Luis guamushigLuis guamushig
106
$endgroup$
closed as unclear what you're asking by Peter, Cesareo, José Carlos Santos, Lord_Farin, Namaste Jan 11 at 18:37
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
|
show 1 more comment
$begingroup$
Is it possible to place 2019 natural numbers along a circumference so that, for any two of these numbers, the proportion of the largest to the least is a prime number?
Ok, what I am clear about this problem is that for the ratio to be a number first, it means that given any two numbers, its mcd can not be 1, because in this way we make sure that at least the proportion is a natural number ... However, I am not very clear on how to interpret the part in which it says that they are located along a circumference, that is, How different is it if we place it on a straight?
number-theory
edited Jan 11 at 8:49
Yuval Filmus
48.7k472145
asked Jan 11 at 6:39
Luis guamushigLuis guamushig
106
$endgroup$
closed as unclear what you're asking by Peter, Cesareo, José Carlos Santos, Lord_Farin, Namaste Jan 11 at 18:37
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
3
$begingroup$
This looks like a competition problem. Is it a competition problem? Where is it from?
$endgroup$
– Arthur
Jan 11 at 6:41
1
$begingroup$
Let's see if I understood the question, so let's start with just 3 numbers $a<b<c$, so if I pick up any 2 of them, their proportion should be prime. So let $frac{c}{a}=m$, $frac{c}{b}=n$, $frac{b}{a}=k$, where $k,m,n$ are prime, then $k=frac{m}{n}$ which tells us that it is impossible to place 3 natural numbers using above requirements
$endgroup$
– Lee
Jan 11 at 6:49
1
$begingroup$
maybe you have to check the question again, it is stated a little bit strangely
$endgroup$
– Lee
Jan 11 at 6:52
1
$begingroup$
Are we comparing any pair of numbers ? Or only pairs that are neighbours reading round the circle ? The questions as stated doesn't say we only compare neighbours, but without this restriction the question doesn't make sense.
$endgroup$
– gandalf61
Jan 11 at 10:18
$begingroup$
Yes, it is a question of competence (mathematical olimpadas), because it was written like that, I said 2019 natural numbers, they do not clarify much of what order or something, so my question, I still do not understand why necessarily in a circle
$endgroup$
– Luis guamushig
Jan 12 at 23:08
|
show 1 more comment
$begingroup$
Is it possible to place 2019 natural numbers along a circumference so that, for any two of these numbers, the proportion of the largest to the least is a prime number?
Ok, what I am clear about this problem is that for the ratio to be a number first, it means that given any two numbers, its mcd can not be 1, because in this way we make sure that at least the proportion is a natural number ... However, I am not very clear on how to interpret the part in which it says that they are located along a circumference, that is, How different is it if we place it on a straight?
number-theory
edited Jan 11 at 8:49
Yuval Filmus
48.7k472145
asked Jan 11 at 6:39
Luis guamushigLuis guamushig
106
$endgroup$
Is it possible to place 2019 natural numbers along a circumference so that, for any two of these numbers, the proportion of the largest to the least is a prime number?
Ok, what I am clear about this problem is that for the ratio to be a number first, it means that given any two numbers, its mcd can not be 1, because in this way we make sure that at least the proportion is a natural number ... However, I am not very clear on how to interpret the part in which it says that they are located along a circumference, that is, How different is it if we place it on a straight?
number-theory
number-theory
edited Jan 11 at 8:49
Yuval Filmus
48.7k472145
asked Jan 11 at 6:39
Luis guamushigLuis guamushig
106
edited Jan 11 at 8:49
Yuval Filmus
48.7k472145
asked Jan 11 at 6:39
Luis guamushigLuis guamushig
106
edited Jan 11 at 8:49
Yuval Filmus
48.7k472145
edited Jan 11 at 8:49
Yuval Filmus
48.7k472145
edited Jan 11 at 8:49
Yuval Filmus
48.7k472145
48.7k472145
asked Jan 11 at 6:39
Luis guamushigLuis guamushig
106
asked Jan 11 at 6:39
Luis guamushigLuis guamushig
106
asked Jan 11 at 6:39
Luis guamushigLuis guamushig
106
106
closed as unclear what you're asking by Peter, Cesareo, José Carlos Santos, Lord_Farin, Namaste Jan 11 at 18:37
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
closed as unclear what you're asking by Peter, Cesareo, José Carlos Santos, Lord_Farin, Namaste Jan 11 at 18:37
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
3
$begingroup$
This looks like a competition problem. Is it a competition problem? Where is it from?
$endgroup$
– Arthur
Jan 11 at 6:41
1
$begingroup$
Let's see if I understood the question, so let's start with just 3 numbers $a<b<c$, so if I pick up any 2 of them, their proportion should be prime. So let $frac{c}{a}=m$, $frac{c}{b}=n$, $frac{b}{a}=k$, where $k,m,n$ are prime, then $k=frac{m}{n}$ which tells us that it is impossible to place 3 natural numbers using above requirements
$endgroup$
– Lee
Jan 11 at 6:49
1
$begingroup$
maybe you have to check the question again, it is stated a little bit strangely
$endgroup$
– Lee
Jan 11 at 6:52
1
$begingroup$
Are we comparing any pair of numbers ? Or only pairs that are neighbours reading round the circle ? The questions as stated doesn't say we only compare neighbours, but without this restriction the question doesn't make sense.
$endgroup$
– gandalf61
Jan 11 at 10:18
$begingroup$
Yes, it is a question of competence (mathematical olimpadas), because it was written like that, I said 2019 natural numbers, they do not clarify much of what order or something, so my question, I still do not understand why necessarily in a circle
$endgroup$
– Luis guamushig
Jan 12 at 23:08
|
show 1 more comment
3
$begingroup$
This looks like a competition problem. Is it a competition problem? Where is it from?
$endgroup$
– Arthur
Jan 11 at 6:41
1
$begingroup$
Let's see if I understood the question, so let's start with just 3 numbers $a<b<c$, so if I pick up any 2 of them, their proportion should be prime. So let $frac{c}{a}=m$, $frac{c}{b}=n$, $frac{b}{a}=k$, where $k,m,n$ are prime, then $k=frac{m}{n}$ which tells us that it is impossible to place 3 natural numbers using above requirements
$endgroup$
– Lee
Jan 11 at 6:49
1
$begingroup$
maybe you have to check the question again, it is stated a little bit strangely
$endgroup$
– Lee
Jan 11 at 6:52
1
$begingroup$
Are we comparing any pair of numbers ? Or only pairs that are neighbours reading round the circle ? The questions as stated doesn't say we only compare neighbours, but without this restriction the question doesn't make sense.
$endgroup$
– gandalf61
Jan 11 at 10:18
$begingroup$
Yes, it is a question of competence (mathematical olimpadas), because it was written like that, I said 2019 natural numbers, they do not clarify much of what order or something, so my question, I still do not understand why necessarily in a circle
$endgroup$
– Luis guamushig
Jan 12 at 23:08
3
3
$begingroup$
This looks like a competition problem. Is it a competition problem? Where is it from?
$endgroup$
– Arthur
Jan 11 at 6:41
$begingroup$
This looks like a competition problem. Is it a competition problem? Where is it from?
$endgroup$
– Arthur
Jan 11 at 6:41
1
1
$begingroup$
Let's see if I understood the question, so let's start with just 3 numbers $a<b<c$, so if I pick up any 2 of them, their proportion should be prime. So let $frac{c}{a}=m$, $frac{c}{b}=n$, $frac{b}{a}=k$, where $k,m,n$ are prime, then $k=frac{m}{n}$ which tells us that it is impossible to place 3 natural numbers using above requirements
$endgroup$
– Lee
Jan 11 at 6:49
$begingroup$
Let's see if I understood the question, so let's start with just 3 numbers $a<b<c$, so if I pick up any 2 of them, their proportion should be prime. So let $frac{c}{a}=m$, $frac{c}{b}=n$, $frac{b}{a}=k$, where $k,m,n$ are prime, then $k=frac{m}{n}$ which tells us that it is impossible to place 3 natural numbers using above requirements
$endgroup$
– Lee
Jan 11 at 6:49
1
1
$begingroup$
maybe you have to check the question again, it is stated a little bit strangely
$endgroup$
– Lee
Jan 11 at 6:52
$begingroup$
maybe you have to check the question again, it is stated a little bit strangely
$endgroup$
– Lee
Jan 11 at 6:52
1
1
$begingroup$
Are we comparing any pair of numbers ? Or only pairs that are neighbours reading round the circle ? The questions as stated doesn't say we only compare neighbours, but without this restriction the question doesn't make sense.
$endgroup$
– gandalf61
Jan 11 at 10:18
$begingroup$
Are we comparing any pair of numbers ? Or only pairs that are neighbours reading round the circle ? The questions as stated doesn't say we only compare neighbours, but without this restriction the question doesn't make sense.
$endgroup$
– gandalf61
Jan 11 at 10:18
$begingroup$
Yes, it is a question of competence (mathematical olimpadas), because it was written like that, I said 2019 natural numbers, they do not clarify much of what order or something, so my question, I still do not understand why necessarily in a circle
$endgroup$
– Luis guamushig
Jan 12 at 23:08
$begingroup$
Yes, it is a question of competence (mathematical olimpadas), because it was written like that, I said 2019 natural numbers, they do not clarify much of what order or something, so my question, I still do not understand why necessarily in a circle
$endgroup$
– Luis guamushig
Jan 12 at 23:08
|
show 1 more comment
1 Answer
1
active
oldest
votes
$begingroup$
Let us denote the numbers by $x_0,ldots,x_{m-1}$, where in your case $m = 2019$. Let $P(x)$ denote the number of prime factors of $x$. Your condition implies that $P(x_i) = P(x_{i+1}) pm 1$, and in particular $P(x_i) equiv P(x_{i+1}) + 1 pmod{2}$, where the indices are modulo $m$. Summing this over all $i$, we get the contradictory $0 equiv 1 pmod{2}$, since $m$ is odd.
In contrast, if $m$ is even, then there is always a solution. I will illustrate this with $m = 6$:
$$
1,2,4,8,4,2.
$$
The general solution is similar.
answered Jan 11 at 8:49
Yuval FilmusYuval Filmus
48.7k472145
$endgroup$
$begingroup$
You guys are sure in a very supportive mood... no wonder I stopped participating.
$endgroup$
– Yuval Filmus
Jan 11 at 10:37
$begingroup$
or in general, we can get the ratio between the largest and the smallest to be a prime number if and only if the number of natural numbers located in the circumference is even
$endgroup$
– Luis guamushig
Jan 12 at 23:24
$begingroup$
It's like that, right?
$endgroup$
– Luis guamushig
Jan 12 at 23:25
$begingroup$
Right, it depends only on the parity.
$endgroup$
– Yuval Filmus
Jan 13 at 6:32
$begingroup$
Why mod 2? because the indices are two?
$endgroup$
– Luis guamushig
Jan 14 at 6:24
|
show 3 more comments
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Let us denote the numbers by $x_0,ldots,x_{m-1}$, where in your case $m = 2019$. Let $P(x)$ denote the number of prime factors of $x$. Your condition implies that $P(x_i) = P(x_{i+1}) pm 1$, and in particular $P(x_i) equiv P(x_{i+1}) + 1 pmod{2}$, where the indices are modulo $m$. Summing this over all $i$, we get the contradictory $0 equiv 1 pmod{2}$, since $m$ is odd.
In contrast, if $m$ is even, then there is always a solution. I will illustrate this with $m = 6$:
$$
1,2,4,8,4,2.
$$
The general solution is similar.
answered Jan 11 at 8:49
Yuval FilmusYuval Filmus
48.7k472145
$endgroup$
$begingroup$
You guys are sure in a very supportive mood... no wonder I stopped participating.
$endgroup$
– Yuval Filmus
Jan 11 at 10:37
$begingroup$
or in general, we can get the ratio between the largest and the smallest to be a prime number if and only if the number of natural numbers located in the circumference is even
$endgroup$
– Luis guamushig
Jan 12 at 23:24
$begingroup$
It's like that, right?
$endgroup$
– Luis guamushig
Jan 12 at 23:25
$begingroup$
Right, it depends only on the parity.
$endgroup$
– Yuval Filmus
Jan 13 at 6:32
$begingroup$
Why mod 2? because the indices are two?
$endgroup$
– Luis guamushig
Jan 14 at 6:24
|
show 3 more comments
$begingroup$
Let us denote the numbers by $x_0,ldots,x_{m-1}$, where in your case $m = 2019$. Let $P(x)$ denote the number of prime factors of $x$. Your condition implies that $P(x_i) = P(x_{i+1}) pm 1$, and in particular $P(x_i) equiv P(x_{i+1}) + 1 pmod{2}$, where the indices are modulo $m$. Summing this over all $i$, we get the contradictory $0 equiv 1 pmod{2}$, since $m$ is odd.
In contrast, if $m$ is even, then there is always a solution. I will illustrate this with $m = 6$:
$$
1,2,4,8,4,2.
$$
The general solution is similar.
answered Jan 11 at 8:49
Yuval FilmusYuval Filmus
48.7k472145
$endgroup$
$begingroup$
You guys are sure in a very supportive mood... no wonder I stopped participating.
$endgroup$
– Yuval Filmus
Jan 11 at 10:37
$begingroup$
or in general, we can get the ratio between the largest and the smallest to be a prime number if and only if the number of natural numbers located in the circumference is even
$endgroup$
– Luis guamushig
Jan 12 at 23:24
$begingroup$
It's like that, right?
$endgroup$
– Luis guamushig
Jan 12 at 23:25
$begingroup$
Right, it depends only on the parity.
$endgroup$
– Yuval Filmus
Jan 13 at 6:32
$begingroup$
Why mod 2? because the indices are two?
$endgroup$
– Luis guamushig
Jan 14 at 6:24
|
show 3 more comments
$begingroup$
Let us denote the numbers by $x_0,ldots,x_{m-1}$, where in your case $m = 2019$. Let $P(x)$ denote the number of prime factors of $x$. Your condition implies that $P(x_i) = P(x_{i+1}) pm 1$, and in particular $P(x_i) equiv P(x_{i+1}) + 1 pmod{2}$, where the indices are modulo $m$. Summing this over all $i$, we get the contradictory $0 equiv 1 pmod{2}$, since $m$ is odd.
In contrast, if $m$ is even, then there is always a solution. I will illustrate this with $m = 6$:
$$
1,2,4,8,4,2.
$$
The general solution is similar.
answered Jan 11 at 8:49
Yuval FilmusYuval Filmus
48.7k472145
$endgroup$
Let us denote the numbers by $x_0,ldots,x_{m-1}$, where in your case $m = 2019$. Let $P(x)$ denote the number of prime factors of $x$. Your condition implies that $P(x_i) = P(x_{i+1}) pm 1$, and in particular $P(x_i) equiv P(x_{i+1}) + 1 pmod{2}$, where the indices are modulo $m$. Summing this over all $i$, we get the contradictory $0 equiv 1 pmod{2}$, since $m$ is odd.
In contrast, if $m$ is even, then there is always a solution. I will illustrate this with $m = 6$:
$$
1,2,4,8,4,2.
$$
The general solution is similar.
answered Jan 11 at 8:49
Yuval FilmusYuval Filmus
48.7k472145
answered Jan 11 at 8:49
Yuval FilmusYuval Filmus
48.7k472145
answered Jan 11 at 8:49
Yuval FilmusYuval Filmus
48.7k472145
answered Jan 11 at 8:49
Yuval FilmusYuval Filmus
48.7k472145
48.7k472145
$begingroup$
You guys are sure in a very supportive mood... no wonder I stopped participating.
$endgroup$
– Yuval Filmus
Jan 11 at 10:37
$begingroup$
or in general, we can get the ratio between the largest and the smallest to be a prime number if and only if the number of natural numbers located in the circumference is even
$endgroup$
– Luis guamushig
Jan 12 at 23:24
$begingroup$
It's like that, right?
$endgroup$
– Luis guamushig
Jan 12 at 23:25
$begingroup$
Right, it depends only on the parity.
$endgroup$
– Yuval Filmus
Jan 13 at 6:32
$begingroup$
Why mod 2? because the indices are two?
$endgroup$
– Luis guamushig
Jan 14 at 6:24
|
show 3 more comments
$begingroup$
You guys are sure in a very supportive mood... no wonder I stopped participating.
$endgroup$
– Yuval Filmus
Jan 11 at 10:37
$begingroup$
or in general, we can get the ratio between the largest and the smallest to be a prime number if and only if the number of natural numbers located in the circumference is even
$endgroup$
– Luis guamushig
Jan 12 at 23:24
$begingroup$
It's like that, right?
$endgroup$
– Luis guamushig
Jan 12 at 23:25
$begingroup$
Right, it depends only on the parity.
$endgroup$
– Yuval Filmus
Jan 13 at 6:32
$begingroup$
Why mod 2? because the indices are two?
$endgroup$
– Luis guamushig
Jan 14 at 6:24
$begingroup$
You guys are sure in a very supportive mood... no wonder I stopped participating.
$endgroup$
– Yuval Filmus
Jan 11 at 10:37
$begingroup$
You guys are sure in a very supportive mood... no wonder I stopped participating.
$endgroup$
– Yuval Filmus
Jan 11 at 10:37
$begingroup$
or in general, we can get the ratio between the largest and the smallest to be a prime number if and only if the number of natural numbers located in the circumference is even
$endgroup$
– Luis guamushig
Jan 12 at 23:24
$begingroup$
or in general, we can get the ratio between the largest and the smallest to be a prime number if and only if the number of natural numbers located in the circumference is even
$endgroup$
– Luis guamushig
Jan 12 at 23:24
$begingroup$
It's like that, right?
$endgroup$
– Luis guamushig
Jan 12 at 23:25
$begingroup$
It's like that, right?
$endgroup$
– Luis guamushig
Jan 12 at 23:25
$begingroup$
Right, it depends only on the parity.
$endgroup$
– Yuval Filmus
Jan 13 at 6:32
$begingroup$
Right, it depends only on the parity.
$endgroup$
– Yuval Filmus
Jan 13 at 6:32
$begingroup$
Why mod 2? because the indices are two?
$endgroup$
– Luis guamushig
Jan 14 at 6:24
$begingroup$
Why mod 2? because the indices are two?
$endgroup$
– Luis guamushig
Jan 14 at 6:24
|
show 3 more comments
3
$begingroup$
This looks like a competition problem. Is it a competition problem? Where is it from?
$endgroup$
– Arthur
Jan 11 at 6:41
1
$begingroup$
Let's see if I understood the question, so let's start with just 3 numbers $a<b<c$, so if I pick up any 2 of them, their proportion should be prime. So let $frac{c}{a}=m$, $frac{c}{b}=n$, $frac{b}{a}=k$, where $k,m,n$ are prime, then $k=frac{m}{n}$ which tells us that it is impossible to place 3 natural numbers using above requirements
$endgroup$
– Lee
Jan 11 at 6:49
1
$begingroup$
maybe you have to check the question again, it is stated a little bit strangely
$endgroup$
– Lee
Jan 11 at 6:52
1
$begingroup$
Are we comparing any pair of numbers ? Or only pairs that are neighbours reading round the circle ? The questions as stated doesn't say we only compare neighbours, but without this restriction the question doesn't make sense.
$endgroup$
– gandalf61
Jan 11 at 10:18
$begingroup$
Yes, it is a question of competence (mathematical olimpadas), because it was written like that, I said 2019 natural numbers, they do not clarify much of what order or something, so my question, I still do not understand why necessarily in a circle
$endgroup$
– Luis guamushig
Jan 12 at 23:08