Mixing
Sequence of N numbers
$begingroup$
We are given a number $N$ such that $3 leq N leq 50000,$
and we have to find a sequence consisting of $N$ numbers, where:
All numbers are distinct;
All numbers lie between $1$ to $10^{19}$;
Two adjacent numbers are NOT co-prime;
Three adjacent numbers are co-prime.
Note that in this array if the sequence is $S_0,S_1,S_2,...,S_n$, we consider $S_1$ to be adjacent to $S_n$. So, $S_{n-1},S_0,S_1$ should have $gcd=1$. Similarly, $S_{n-1}$ and $S_0$ should have a $gcd$ of more than 1. Same goes for $S_{n-2}$ as well.
Example: If $N=3$, then our sequence can be 6 15 10 since $gcd(6,15,10)=1, gcd(6,15)$ and $gcd(10,15)$ is not 1.
My approach: I generated prime numbers up to $N$ using an algorithm. I multiply all the elements to the element on its right and finally multiply the rightmost ($S_{n-1}$) element by 2.
For example, if $N=4$:
- Step 1 (Generating primes): 2 3 5 7
- Step 2 (multiplying): 6 15 35 14
which is my required sequence. But in the question, $N$ can be as large as $50000$ and the elements should be in the range $[1,10^9]$. By using my approach, I am missing out some primes in between like 10, 14, etc.
How can I make a better algorithm? Also I have to write "Impossible" in case making the sequence isn't possible. I can't find what will be the condition when we can't make the sequence.
Can anyone suggest anything better?
sequences-and-series prime-numbers coprime
edited Jan 6 at 18:45
amWhy
1
asked Jan 6 at 18:21
Rizwan AnsariRizwan Ansari
83
$endgroup$
add a comment |
$begingroup$
We are given a number $N$ such that $3 leq N leq 50000,$
and we have to find a sequence consisting of $N$ numbers, where:
All numbers are distinct;
All numbers lie between $1$ to $10^{19}$;
Two adjacent numbers are NOT co-prime;
Three adjacent numbers are co-prime.
Note that in this array if the sequence is $S_0,S_1,S_2,...,S_n$, we consider $S_1$ to be adjacent to $S_n$. So, $S_{n-1},S_0,S_1$ should have $gcd=1$. Similarly, $S_{n-1}$ and $S_0$ should have a $gcd$ of more than 1. Same goes for $S_{n-2}$ as well.
Example: If $N=3$, then our sequence can be 6 15 10 since $gcd(6,15,10)=1, gcd(6,15)$ and $gcd(10,15)$ is not 1.
My approach: I generated prime numbers up to $N$ using an algorithm. I multiply all the elements to the element on its right and finally multiply the rightmost ($S_{n-1}$) element by 2.
For example, if $N=4$:
- Step 1 (Generating primes): 2 3 5 7
- Step 2 (multiplying): 6 15 35 14
which is my required sequence. But in the question, $N$ can be as large as $50000$ and the elements should be in the range $[1,10^9]$. By using my approach, I am missing out some primes in between like 10, 14, etc.
How can I make a better algorithm? Also I have to write "Impossible" in case making the sequence isn't possible. I can't find what will be the condition when we can't make the sequence.
Can anyone suggest anything better?
sequences-and-series prime-numbers coprime
edited Jan 6 at 18:45
amWhy
1
asked Jan 6 at 18:21
Rizwan AnsariRizwan Ansari
83
$endgroup$
add a comment |
$begingroup$
We are given a number $N$ such that $3 leq N leq 50000,$
and we have to find a sequence consisting of $N$ numbers, where:
All numbers are distinct;
All numbers lie between $1$ to $10^{19}$;
Two adjacent numbers are NOT co-prime;
Three adjacent numbers are co-prime.
Note that in this array if the sequence is $S_0,S_1,S_2,...,S_n$, we consider $S_1$ to be adjacent to $S_n$. So, $S_{n-1},S_0,S_1$ should have $gcd=1$. Similarly, $S_{n-1}$ and $S_0$ should have a $gcd$ of more than 1. Same goes for $S_{n-2}$ as well.
Example: If $N=3$, then our sequence can be 6 15 10 since $gcd(6,15,10)=1, gcd(6,15)$ and $gcd(10,15)$ is not 1.
My approach: I generated prime numbers up to $N$ using an algorithm. I multiply all the elements to the element on its right and finally multiply the rightmost ($S_{n-1}$) element by 2.
For example, if $N=4$:
- Step 1 (Generating primes): 2 3 5 7
- Step 2 (multiplying): 6 15 35 14
which is my required sequence. But in the question, $N$ can be as large as $50000$ and the elements should be in the range $[1,10^9]$. By using my approach, I am missing out some primes in between like 10, 14, etc.
How can I make a better algorithm? Also I have to write "Impossible" in case making the sequence isn't possible. I can't find what will be the condition when we can't make the sequence.
Can anyone suggest anything better?
sequences-and-series prime-numbers coprime
edited Jan 6 at 18:45
amWhy
1
asked Jan 6 at 18:21
Rizwan AnsariRizwan Ansari
83
$endgroup$
We are given a number $N$ such that $3 leq N leq 50000,$
and we have to find a sequence consisting of $N$ numbers, where:
All numbers are distinct;
All numbers lie between $1$ to $10^{19}$;
Two adjacent numbers are NOT co-prime;
Three adjacent numbers are co-prime.
Note that in this array if the sequence is $S_0,S_1,S_2,...,S_n$, we consider $S_1$ to be adjacent to $S_n$. So, $S_{n-1},S_0,S_1$ should have $gcd=1$. Similarly, $S_{n-1}$ and $S_0$ should have a $gcd$ of more than 1. Same goes for $S_{n-2}$ as well.
Example: If $N=3$, then our sequence can be 6 15 10 since $gcd(6,15,10)=1, gcd(6,15)$ and $gcd(10,15)$ is not 1.
My approach: I generated prime numbers up to $N$ using an algorithm. I multiply all the elements to the element on its right and finally multiply the rightmost ($S_{n-1}$) element by 2.
For example, if $N=4$:
- Step 1 (Generating primes): 2 3 5 7
- Step 2 (multiplying): 6 15 35 14
which is my required sequence. But in the question, $N$ can be as large as $50000$ and the elements should be in the range $[1,10^9]$. By using my approach, I am missing out some primes in between like 10, 14, etc.
How can I make a better algorithm? Also I have to write "Impossible" in case making the sequence isn't possible. I can't find what will be the condition when we can't make the sequence.
Can anyone suggest anything better?
sequences-and-series prime-numbers coprime
sequences-and-series prime-numbers coprime
edited Jan 6 at 18:45
amWhy
1
asked Jan 6 at 18:21
Rizwan AnsariRizwan Ansari
83
edited Jan 6 at 18:45
amWhy
1
asked Jan 6 at 18:21
Rizwan AnsariRizwan Ansari
83
edited Jan 6 at 18:45
amWhy
1
edited Jan 6 at 18:45
amWhy
1
edited Jan 6 at 18:45
amWhy
1
1
asked Jan 6 at 18:21
Rizwan AnsariRizwan Ansari
83
asked Jan 6 at 18:21
Rizwan AnsariRizwan Ansari
83
asked Jan 6 at 18:21
Rizwan AnsariRizwan Ansari
83
83
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Consider $1001$ primes lower than $10000$ (it is possible, look on the internet). Consider the complete graph such that all they are its vertices. Every vertex has an even degree, therefore the graph has a cyclic path $P$ that goed exactly once through every edge.
In your array, take as $i$-th number the product of the two primes that are the vertices of the $i$-th edge in $P$. The array has size $500*1001$, keep the first $N$ elements.
Since $P$ goes exactly once through each edge, the elements of the array are pairwise distinct.
Since every element is the product of two primes lower than $10000$, no element is higher than $10^8$.
Since $P$ is a path, no two consecutive elements are coprime.
For three consecutive elements not to be coprime, you would need three consecutives edges in $P$ that have a common vertex, this is absurd.
Edit: with five primes 2,3,5,7,11;
A fitting path is (2,3), (3,5), (5,2), (2,7), (7,11), (11,3), (3,7), (7,5), (5,11), (11,2) (draw the graph).
The sequence is 6 15 10 14 77 33 21 35 55 22.
answered Jan 6 at 18:35
MindlackMindlack
3,29217
$endgroup$
$begingroup$
can you give an example with a smaller value of N?
$endgroup$
– Rizwan Ansari
Jan 6 at 19:22
$begingroup$
Efficient way/algorithm to fill my array?
$endgroup$
– Rizwan Ansari
Jan 6 at 20:34
$begingroup$
What you need is an efficient way of generatating the circuit $P$. I suggest that you have a look at this : en.m.wikipedia.org/wiki/Eulerian_path
$endgroup$
– Mindlack
Jan 6 at 20:36
add a comment |
$begingroup$
As your original method of multiplying consecutive pairs of a cyclic sequence of $N$ primes works nicely as long as $N$ is small, we may assume $Nge 6$ in what follows and write $N=3L+r$ with $0le rle 2$.
Start with the sequence $2,3,4,ldots, M$ for suitable $M$ (see below), strike out all multiples of $2$, strike out all multiples of $3$, strike out all multiples of $5$. This produces a shortened sequence $a_1,a_2,a_3,ldots$.
This sequence contains all primes (in particular, we have $a_1=7$, $a_2=11$, $a_3=13$) but also many composite numbers (the first being $49$).
We always have $a_{k+1}le a_k+6$ because among the $6$ consecutive integers $a_k+1,ldots, a_k+6$, we strike at most three evens, at most one odd multiple of $3$, and at most one odd multiple of $5$, hence at least one "survives". That implies $gcd(a_{k+1},a_k)le 6$ and as the numbers are not divisible by $2,3,5$, we see that $a_k, a_{k+1}$ are co-prime.
Now we produce the sequence
$$tag16,10,15,;6a_1,10a_2,15a_1,;6a_2,10a_1,15a_2,; 6a_3,10a_4,15a_3,;6a_4,10a_3,15a_4,;ldots$$
of length $3L$, i.e., it ends in terms of the form $6a_k,10a_{kpm1},15a_k$.
We see that any two consecutive terms in $(1)$ have greatest common divisor $2,5,3$ and so on in cyclic order, and that any three consecutive terms are co-prime.
From $a_1,ldots, a_{2n}$ we can produce a sequence of length $3+6n$, hence in worst case need $a_{16666}$. To this end, we start with $Mge 16666cdot frac 21cdot frac 32cdot frac 54$, i.e., with $M=62497$.
Note that this makes all terms of our sequence $<10^6$.
To our satisfaction, the wrap-around already looks like this (with pairwise and triplewise gcd indicated in the lower rows):
$$ begin{matrix}ldots&,& 6a_k&,& 10a_{kpm1}&,&15a_k&|&6&,&10&,&15&,&ldots\
&3&&2&&5&&3&&2&&5&&3\
&&1&&1&&1&&1&&1&&1&&end{matrix}$$
Therefore we are already done if $r=0$.
If $r=1$, we make a minor adjustment near the beginning of $(1)$, i.e., we replace the first six terms $6,10,15,42,110,105$ with these seven terms
$$ begin{matrix}6&,&10&,&15&,&color{red}{21}&,&color{red}{77}&,&110&,& 105&,&ldots\
&2&&5&&3&&7&&11&&5&&3\
&&1&&1&&1&&1&&1&&1&&end{matrix}$$
Finally, if $r=2$, we replace the first six terms $6,10,15,42,110,105$ with these eight terms
$$ begin{matrix}
6&,&10&,&15&,& color{red}{33 }&,& color{red}{77} &,& color{red}{14 }&,&110&,&105&,&ldots
\&2&&5&&3&&11&&7&&2&&5&&3\
&&1&&1&&1&&1&&1&&1&&1
end{matrix}$$
Note that the terms in red do not occur elsewhere in the sequence, hence we still have all terms distinct.
Remarks:
It is possible to algorithmically produce the sequence above in $O(N)$ time with $O(1)$ memory as one does not even have to store the sieve (i.e., the sequence $a_1,a_2,ldots$ can be generated on the fly).
The maximum term in the sequence is of size $O(N)$ with a constant small enough (by a great margin) to satisfy the constraints of the problem statement. The sequence could be made much longer without increasing the maximum term (e.g., we could use $12a_1,20a_2,45a_1$ as additional triple); I suspect that the maximum term can be made $O(sqrt N)$.
answered Jan 6 at 18:28
Hagen von EitzenHagen von Eitzen
278k22269497
$endgroup$
$begingroup$
suppose N=4 Sequence would be: 6,10,15,14 but gcd(14,6,10) is not 1. Any way to solve this out?
$endgroup$
– Rizwan Ansari
Jan 6 at 18:46
$begingroup$
Why should it matter that $gcd(14,6,10)>1$? These are not three consecutive terms
$endgroup$
– Hagen von Eitzen
Jan 6 at 18:51
$begingroup$
If my question wasn't clear : Ai , A(i+1) mod N, A(i+2) mod N are adjacent to each other
$endgroup$
– Rizwan Ansari
Jan 6 at 18:54
$begingroup$
@RizwanAnsariOops, I overread that condition. Will adjust quickly
$endgroup$
– Hagen von Eitzen
Jan 6 at 18:56
$begingroup$
for N=6, Sequence: 6,10,15,12,30,75 but gcd(15,12,30) isn't 1. Fails without cycle as well :/
$endgroup$
– Rizwan Ansari
Jan 6 at 19:25
|
show 2 more comments
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',
autoActivateHeartbeat: false,
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
});
}
});
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%2f3064225%2fsequence-of-n-numbers%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
$begingroup$
Consider $1001$ primes lower than $10000$ (it is possible, look on the internet). Consider the complete graph such that all they are its vertices. Every vertex has an even degree, therefore the graph has a cyclic path $P$ that goed exactly once through every edge.
In your array, take as $i$-th number the product of the two primes that are the vertices of the $i$-th edge in $P$. The array has size $500*1001$, keep the first $N$ elements.
Since $P$ goes exactly once through each edge, the elements of the array are pairwise distinct.
Since every element is the product of two primes lower than $10000$, no element is higher than $10^8$.
Since $P$ is a path, no two consecutive elements are coprime.
For three consecutive elements not to be coprime, you would need three consecutives edges in $P$ that have a common vertex, this is absurd.
Edit: with five primes 2,3,5,7,11;
A fitting path is (2,3), (3,5), (5,2), (2,7), (7,11), (11,3), (3,7), (7,5), (5,11), (11,2) (draw the graph).
The sequence is 6 15 10 14 77 33 21 35 55 22.
answered Jan 6 at 18:35
MindlackMindlack
3,29217
$endgroup$
$begingroup$
can you give an example with a smaller value of N?
$endgroup$
– Rizwan Ansari
Jan 6 at 19:22
$begingroup$
Efficient way/algorithm to fill my array?
$endgroup$
– Rizwan Ansari
Jan 6 at 20:34
$begingroup$
What you need is an efficient way of generatating the circuit $P$. I suggest that you have a look at this : en.m.wikipedia.org/wiki/Eulerian_path
$endgroup$
– Mindlack
Jan 6 at 20:36
add a comment |
$begingroup$
Consider $1001$ primes lower than $10000$ (it is possible, look on the internet). Consider the complete graph such that all they are its vertices. Every vertex has an even degree, therefore the graph has a cyclic path $P$ that goed exactly once through every edge.
In your array, take as $i$-th number the product of the two primes that are the vertices of the $i$-th edge in $P$. The array has size $500*1001$, keep the first $N$ elements.
Since $P$ goes exactly once through each edge, the elements of the array are pairwise distinct.
Since every element is the product of two primes lower than $10000$, no element is higher than $10^8$.
Since $P$ is a path, no two consecutive elements are coprime.
For three consecutive elements not to be coprime, you would need three consecutives edges in $P$ that have a common vertex, this is absurd.
Edit: with five primes 2,3,5,7,11;
A fitting path is (2,3), (3,5), (5,2), (2,7), (7,11), (11,3), (3,7), (7,5), (5,11), (11,2) (draw the graph).
The sequence is 6 15 10 14 77 33 21 35 55 22.
answered Jan 6 at 18:35
MindlackMindlack
3,29217
$endgroup$
$begingroup$
can you give an example with a smaller value of N?
$endgroup$
– Rizwan Ansari
Jan 6 at 19:22
$begingroup$
Efficient way/algorithm to fill my array?
$endgroup$
– Rizwan Ansari
Jan 6 at 20:34
$begingroup$
What you need is an efficient way of generatating the circuit $P$. I suggest that you have a look at this : en.m.wikipedia.org/wiki/Eulerian_path
$endgroup$
– Mindlack
Jan 6 at 20:36
add a comment |
$begingroup$
Consider $1001$ primes lower than $10000$ (it is possible, look on the internet). Consider the complete graph such that all they are its vertices. Every vertex has an even degree, therefore the graph has a cyclic path $P$ that goed exactly once through every edge.
In your array, take as $i$-th number the product of the two primes that are the vertices of the $i$-th edge in $P$. The array has size $500*1001$, keep the first $N$ elements.
Since $P$ goes exactly once through each edge, the elements of the array are pairwise distinct.
Since every element is the product of two primes lower than $10000$, no element is higher than $10^8$.
Since $P$ is a path, no two consecutive elements are coprime.
For three consecutive elements not to be coprime, you would need three consecutives edges in $P$ that have a common vertex, this is absurd.
Edit: with five primes 2,3,5,7,11;
A fitting path is (2,3), (3,5), (5,2), (2,7), (7,11), (11,3), (3,7), (7,5), (5,11), (11,2) (draw the graph).
The sequence is 6 15 10 14 77 33 21 35 55 22.
answered Jan 6 at 18:35
MindlackMindlack
3,29217
$endgroup$
Consider $1001$ primes lower than $10000$ (it is possible, look on the internet). Consider the complete graph such that all they are its vertices. Every vertex has an even degree, therefore the graph has a cyclic path $P$ that goed exactly once through every edge.
In your array, take as $i$-th number the product of the two primes that are the vertices of the $i$-th edge in $P$. The array has size $500*1001$, keep the first $N$ elements.
Since $P$ goes exactly once through each edge, the elements of the array are pairwise distinct.
Since every element is the product of two primes lower than $10000$, no element is higher than $10^8$.
Since $P$ is a path, no two consecutive elements are coprime.
For three consecutive elements not to be coprime, you would need three consecutives edges in $P$ that have a common vertex, this is absurd.
Edit: with five primes 2,3,5,7,11;
A fitting path is (2,3), (3,5), (5,2), (2,7), (7,11), (11,3), (3,7), (7,5), (5,11), (11,2) (draw the graph).
The sequence is 6 15 10 14 77 33 21 35 55 22.
answered Jan 6 at 18:35
MindlackMindlack
3,29217
edited Jan 6 at 20:02
answered Jan 6 at 18:35
MindlackMindlack
3,29217
answered Jan 6 at 18:35
MindlackMindlack
3,29217
answered Jan 6 at 18:35
MindlackMindlack
3,29217
3,29217
$begingroup$
can you give an example with a smaller value of N?
$endgroup$
– Rizwan Ansari
Jan 6 at 19:22
$begingroup$
Efficient way/algorithm to fill my array?
$endgroup$
– Rizwan Ansari
Jan 6 at 20:34
$begingroup$
What you need is an efficient way of generatating the circuit $P$. I suggest that you have a look at this : en.m.wikipedia.org/wiki/Eulerian_path
$endgroup$
– Mindlack
Jan 6 at 20:36
add a comment |
$begingroup$
can you give an example with a smaller value of N?
$endgroup$
– Rizwan Ansari
Jan 6 at 19:22
$begingroup$
Efficient way/algorithm to fill my array?
$endgroup$
– Rizwan Ansari
Jan 6 at 20:34
$begingroup$
What you need is an efficient way of generatating the circuit $P$. I suggest that you have a look at this : en.m.wikipedia.org/wiki/Eulerian_path
$endgroup$
– Mindlack
Jan 6 at 20:36
$begingroup$
can you give an example with a smaller value of N?
$endgroup$
– Rizwan Ansari
Jan 6 at 19:22
$begingroup$
can you give an example with a smaller value of N?
$endgroup$
– Rizwan Ansari
Jan 6 at 19:22
$begingroup$
Efficient way/algorithm to fill my array?
$endgroup$
– Rizwan Ansari
Jan 6 at 20:34
$begingroup$
Efficient way/algorithm to fill my array?
$endgroup$
– Rizwan Ansari
Jan 6 at 20:34
$begingroup$
What you need is an efficient way of generatating the circuit $P$. I suggest that you have a look at this : en.m.wikipedia.org/wiki/Eulerian_path
$endgroup$
– Mindlack
Jan 6 at 20:36
$begingroup$
What you need is an efficient way of generatating the circuit $P$. I suggest that you have a look at this : en.m.wikipedia.org/wiki/Eulerian_path
$endgroup$
– Mindlack
Jan 6 at 20:36
add a comment |
$begingroup$
As your original method of multiplying consecutive pairs of a cyclic sequence of $N$ primes works nicely as long as $N$ is small, we may assume $Nge 6$ in what follows and write $N=3L+r$ with $0le rle 2$.
Start with the sequence $2,3,4,ldots, M$ for suitable $M$ (see below), strike out all multiples of $2$, strike out all multiples of $3$, strike out all multiples of $5$. This produces a shortened sequence $a_1,a_2,a_3,ldots$.
This sequence contains all primes (in particular, we have $a_1=7$, $a_2=11$, $a_3=13$) but also many composite numbers (the first being $49$).
We always have $a_{k+1}le a_k+6$ because among the $6$ consecutive integers $a_k+1,ldots, a_k+6$, we strike at most three evens, at most one odd multiple of $3$, and at most one odd multiple of $5$, hence at least one "survives". That implies $gcd(a_{k+1},a_k)le 6$ and as the numbers are not divisible by $2,3,5$, we see that $a_k, a_{k+1}$ are co-prime.
Now we produce the sequence
$$tag16,10,15,;6a_1,10a_2,15a_1,;6a_2,10a_1,15a_2,; 6a_3,10a_4,15a_3,;6a_4,10a_3,15a_4,;ldots$$
of length $3L$, i.e., it ends in terms of the form $6a_k,10a_{kpm1},15a_k$.
We see that any two consecutive terms in $(1)$ have greatest common divisor $2,5,3$ and so on in cyclic order, and that any three consecutive terms are co-prime.
From $a_1,ldots, a_{2n}$ we can produce a sequence of length $3+6n$, hence in worst case need $a_{16666}$. To this end, we start with $Mge 16666cdot frac 21cdot frac 32cdot frac 54$, i.e., with $M=62497$.
Note that this makes all terms of our sequence $<10^6$.
To our satisfaction, the wrap-around already looks like this (with pairwise and triplewise gcd indicated in the lower rows):
$$ begin{matrix}ldots&,& 6a_k&,& 10a_{kpm1}&,&15a_k&|&6&,&10&,&15&,&ldots\
&3&&2&&5&&3&&2&&5&&3\
&&1&&1&&1&&1&&1&&1&&end{matrix}$$
Therefore we are already done if $r=0$.
If $r=1$, we make a minor adjustment near the beginning of $(1)$, i.e., we replace the first six terms $6,10,15,42,110,105$ with these seven terms
$$ begin{matrix}6&,&10&,&15&,&color{red}{21}&,&color{red}{77}&,&110&,& 105&,&ldots\
&2&&5&&3&&7&&11&&5&&3\
&&1&&1&&1&&1&&1&&1&&end{matrix}$$
Finally, if $r=2$, we replace the first six terms $6,10,15,42,110,105$ with these eight terms
$$ begin{matrix}
6&,&10&,&15&,& color{red}{33 }&,& color{red}{77} &,& color{red}{14 }&,&110&,&105&,&ldots
\&2&&5&&3&&11&&7&&2&&5&&3\
&&1&&1&&1&&1&&1&&1&&1
end{matrix}$$
Note that the terms in red do not occur elsewhere in the sequence, hence we still have all terms distinct.
Remarks:
It is possible to algorithmically produce the sequence above in $O(N)$ time with $O(1)$ memory as one does not even have to store the sieve (i.e., the sequence $a_1,a_2,ldots$ can be generated on the fly).
The maximum term in the sequence is of size $O(N)$ with a constant small enough (by a great margin) to satisfy the constraints of the problem statement. The sequence could be made much longer without increasing the maximum term (e.g., we could use $12a_1,20a_2,45a_1$ as additional triple); I suspect that the maximum term can be made $O(sqrt N)$.
answered Jan 6 at 18:28
Hagen von EitzenHagen von Eitzen
278k22269497
$endgroup$
$begingroup$
suppose N=4 Sequence would be: 6,10,15,14 but gcd(14,6,10) is not 1. Any way to solve this out?
$endgroup$
– Rizwan Ansari
Jan 6 at 18:46
$begingroup$
Why should it matter that $gcd(14,6,10)>1$? These are not three consecutive terms
$endgroup$
– Hagen von Eitzen
Jan 6 at 18:51
$begingroup$
If my question wasn't clear : Ai , A(i+1) mod N, A(i+2) mod N are adjacent to each other
$endgroup$
– Rizwan Ansari
Jan 6 at 18:54
$begingroup$
@RizwanAnsariOops, I overread that condition. Will adjust quickly
$endgroup$
– Hagen von Eitzen
Jan 6 at 18:56
$begingroup$
for N=6, Sequence: 6,10,15,12,30,75 but gcd(15,12,30) isn't 1. Fails without cycle as well :/
$endgroup$
– Rizwan Ansari
Jan 6 at 19:25
|
show 2 more comments
$begingroup$
As your original method of multiplying consecutive pairs of a cyclic sequence of $N$ primes works nicely as long as $N$ is small, we may assume $Nge 6$ in what follows and write $N=3L+r$ with $0le rle 2$.
Start with the sequence $2,3,4,ldots, M$ for suitable $M$ (see below), strike out all multiples of $2$, strike out all multiples of $3$, strike out all multiples of $5$. This produces a shortened sequence $a_1,a_2,a_3,ldots$.
This sequence contains all primes (in particular, we have $a_1=7$, $a_2=11$, $a_3=13$) but also many composite numbers (the first being $49$).
We always have $a_{k+1}le a_k+6$ because among the $6$ consecutive integers $a_k+1,ldots, a_k+6$, we strike at most three evens, at most one odd multiple of $3$, and at most one odd multiple of $5$, hence at least one "survives". That implies $gcd(a_{k+1},a_k)le 6$ and as the numbers are not divisible by $2,3,5$, we see that $a_k, a_{k+1}$ are co-prime.
Now we produce the sequence
$$tag16,10,15,;6a_1,10a_2,15a_1,;6a_2,10a_1,15a_2,; 6a_3,10a_4,15a_3,;6a_4,10a_3,15a_4,;ldots$$
of length $3L$, i.e., it ends in terms of the form $6a_k,10a_{kpm1},15a_k$.
We see that any two consecutive terms in $(1)$ have greatest common divisor $2,5,3$ and so on in cyclic order, and that any three consecutive terms are co-prime.
From $a_1,ldots, a_{2n}$ we can produce a sequence of length $3+6n$, hence in worst case need $a_{16666}$. To this end, we start with $Mge 16666cdot frac 21cdot frac 32cdot frac 54$, i.e., with $M=62497$.
Note that this makes all terms of our sequence $<10^6$.
To our satisfaction, the wrap-around already looks like this (with pairwise and triplewise gcd indicated in the lower rows):
$$ begin{matrix}ldots&,& 6a_k&,& 10a_{kpm1}&,&15a_k&|&6&,&10&,&15&,&ldots\
&3&&2&&5&&3&&2&&5&&3\
&&1&&1&&1&&1&&1&&1&&end{matrix}$$
Therefore we are already done if $r=0$.
If $r=1$, we make a minor adjustment near the beginning of $(1)$, i.e., we replace the first six terms $6,10,15,42,110,105$ with these seven terms
$$ begin{matrix}6&,&10&,&15&,&color{red}{21}&,&color{red}{77}&,&110&,& 105&,&ldots\
&2&&5&&3&&7&&11&&5&&3\
&&1&&1&&1&&1&&1&&1&&end{matrix}$$
Finally, if $r=2$, we replace the first six terms $6,10,15,42,110,105$ with these eight terms
$$ begin{matrix}
6&,&10&,&15&,& color{red}{33 }&,& color{red}{77} &,& color{red}{14 }&,&110&,&105&,&ldots
\&2&&5&&3&&11&&7&&2&&5&&3\
&&1&&1&&1&&1&&1&&1&&1
end{matrix}$$
Note that the terms in red do not occur elsewhere in the sequence, hence we still have all terms distinct.
Remarks:
It is possible to algorithmically produce the sequence above in $O(N)$ time with $O(1)$ memory as one does not even have to store the sieve (i.e., the sequence $a_1,a_2,ldots$ can be generated on the fly).
The maximum term in the sequence is of size $O(N)$ with a constant small enough (by a great margin) to satisfy the constraints of the problem statement. The sequence could be made much longer without increasing the maximum term (e.g., we could use $12a_1,20a_2,45a_1$ as additional triple); I suspect that the maximum term can be made $O(sqrt N)$.
answered Jan 6 at 18:28
Hagen von EitzenHagen von Eitzen
278k22269497
$endgroup$
$begingroup$
suppose N=4 Sequence would be: 6,10,15,14 but gcd(14,6,10) is not 1. Any way to solve this out?
$endgroup$
– Rizwan Ansari
Jan 6 at 18:46
$begingroup$
Why should it matter that $gcd(14,6,10)>1$? These are not three consecutive terms
$endgroup$
– Hagen von Eitzen
Jan 6 at 18:51
$begingroup$
If my question wasn't clear : Ai , A(i+1) mod N, A(i+2) mod N are adjacent to each other
$endgroup$
– Rizwan Ansari
Jan 6 at 18:54
$begingroup$
@RizwanAnsariOops, I overread that condition. Will adjust quickly
$endgroup$
– Hagen von Eitzen
Jan 6 at 18:56
$begingroup$
for N=6, Sequence: 6,10,15,12,30,75 but gcd(15,12,30) isn't 1. Fails without cycle as well :/
$endgroup$
– Rizwan Ansari
Jan 6 at 19:25
|
show 2 more comments
$begingroup$
As your original method of multiplying consecutive pairs of a cyclic sequence of $N$ primes works nicely as long as $N$ is small, we may assume $Nge 6$ in what follows and write $N=3L+r$ with $0le rle 2$.
Start with the sequence $2,3,4,ldots, M$ for suitable $M$ (see below), strike out all multiples of $2$, strike out all multiples of $3$, strike out all multiples of $5$. This produces a shortened sequence $a_1,a_2,a_3,ldots$.
This sequence contains all primes (in particular, we have $a_1=7$, $a_2=11$, $a_3=13$) but also many composite numbers (the first being $49$).
We always have $a_{k+1}le a_k+6$ because among the $6$ consecutive integers $a_k+1,ldots, a_k+6$, we strike at most three evens, at most one odd multiple of $3$, and at most one odd multiple of $5$, hence at least one "survives". That implies $gcd(a_{k+1},a_k)le 6$ and as the numbers are not divisible by $2,3,5$, we see that $a_k, a_{k+1}$ are co-prime.
Now we produce the sequence
$$tag16,10,15,;6a_1,10a_2,15a_1,;6a_2,10a_1,15a_2,; 6a_3,10a_4,15a_3,;6a_4,10a_3,15a_4,;ldots$$
of length $3L$, i.e., it ends in terms of the form $6a_k,10a_{kpm1},15a_k$.
We see that any two consecutive terms in $(1)$ have greatest common divisor $2,5,3$ and so on in cyclic order, and that any three consecutive terms are co-prime.
From $a_1,ldots, a_{2n}$ we can produce a sequence of length $3+6n$, hence in worst case need $a_{16666}$. To this end, we start with $Mge 16666cdot frac 21cdot frac 32cdot frac 54$, i.e., with $M=62497$.
Note that this makes all terms of our sequence $<10^6$.
To our satisfaction, the wrap-around already looks like this (with pairwise and triplewise gcd indicated in the lower rows):
$$ begin{matrix}ldots&,& 6a_k&,& 10a_{kpm1}&,&15a_k&|&6&,&10&,&15&,&ldots\
&3&&2&&5&&3&&2&&5&&3\
&&1&&1&&1&&1&&1&&1&&end{matrix}$$
Therefore we are already done if $r=0$.
If $r=1$, we make a minor adjustment near the beginning of $(1)$, i.e., we replace the first six terms $6,10,15,42,110,105$ with these seven terms
$$ begin{matrix}6&,&10&,&15&,&color{red}{21}&,&color{red}{77}&,&110&,& 105&,&ldots\
&2&&5&&3&&7&&11&&5&&3\
&&1&&1&&1&&1&&1&&1&&end{matrix}$$
Finally, if $r=2$, we replace the first six terms $6,10,15,42,110,105$ with these eight terms
$$ begin{matrix}
6&,&10&,&15&,& color{red}{33 }&,& color{red}{77} &,& color{red}{14 }&,&110&,&105&,&ldots
\&2&&5&&3&&11&&7&&2&&5&&3\
&&1&&1&&1&&1&&1&&1&&1
end{matrix}$$
Note that the terms in red do not occur elsewhere in the sequence, hence we still have all terms distinct.
Remarks:
It is possible to algorithmically produce the sequence above in $O(N)$ time with $O(1)$ memory as one does not even have to store the sieve (i.e., the sequence $a_1,a_2,ldots$ can be generated on the fly).
The maximum term in the sequence is of size $O(N)$ with a constant small enough (by a great margin) to satisfy the constraints of the problem statement. The sequence could be made much longer without increasing the maximum term (e.g., we could use $12a_1,20a_2,45a_1$ as additional triple); I suspect that the maximum term can be made $O(sqrt N)$.
answered Jan 6 at 18:28
Hagen von EitzenHagen von Eitzen
278k22269497
$endgroup$
As your original method of multiplying consecutive pairs of a cyclic sequence of $N$ primes works nicely as long as $N$ is small, we may assume $Nge 6$ in what follows and write $N=3L+r$ with $0le rle 2$.
Start with the sequence $2,3,4,ldots, M$ for suitable $M$ (see below), strike out all multiples of $2$, strike out all multiples of $3$, strike out all multiples of $5$. This produces a shortened sequence $a_1,a_2,a_3,ldots$.
This sequence contains all primes (in particular, we have $a_1=7$, $a_2=11$, $a_3=13$) but also many composite numbers (the first being $49$).
We always have $a_{k+1}le a_k+6$ because among the $6$ consecutive integers $a_k+1,ldots, a_k+6$, we strike at most three evens, at most one odd multiple of $3$, and at most one odd multiple of $5$, hence at least one "survives". That implies $gcd(a_{k+1},a_k)le 6$ and as the numbers are not divisible by $2,3,5$, we see that $a_k, a_{k+1}$ are co-prime.
Now we produce the sequence
$$tag16,10,15,;6a_1,10a_2,15a_1,;6a_2,10a_1,15a_2,; 6a_3,10a_4,15a_3,;6a_4,10a_3,15a_4,;ldots$$
of length $3L$, i.e., it ends in terms of the form $6a_k,10a_{kpm1},15a_k$.
We see that any two consecutive terms in $(1)$ have greatest common divisor $2,5,3$ and so on in cyclic order, and that any three consecutive terms are co-prime.
From $a_1,ldots, a_{2n}$ we can produce a sequence of length $3+6n$, hence in worst case need $a_{16666}$. To this end, we start with $Mge 16666cdot frac 21cdot frac 32cdot frac 54$, i.e., with $M=62497$.
Note that this makes all terms of our sequence $<10^6$.
To our satisfaction, the wrap-around already looks like this (with pairwise and triplewise gcd indicated in the lower rows):
$$ begin{matrix}ldots&,& 6a_k&,& 10a_{kpm1}&,&15a_k&|&6&,&10&,&15&,&ldots\
&3&&2&&5&&3&&2&&5&&3\
&&1&&1&&1&&1&&1&&1&&end{matrix}$$
Therefore we are already done if $r=0$.
If $r=1$, we make a minor adjustment near the beginning of $(1)$, i.e., we replace the first six terms $6,10,15,42,110,105$ with these seven terms
$$ begin{matrix}6&,&10&,&15&,&color{red}{21}&,&color{red}{77}&,&110&,& 105&,&ldots\
&2&&5&&3&&7&&11&&5&&3\
&&1&&1&&1&&1&&1&&1&&end{matrix}$$
Finally, if $r=2$, we replace the first six terms $6,10,15,42,110,105$ with these eight terms
$$ begin{matrix}
6&,&10&,&15&,& color{red}{33 }&,& color{red}{77} &,& color{red}{14 }&,&110&,&105&,&ldots
\&2&&5&&3&&11&&7&&2&&5&&3\
&&1&&1&&1&&1&&1&&1&&1
end{matrix}$$
Note that the terms in red do not occur elsewhere in the sequence, hence we still have all terms distinct.
Remarks:
It is possible to algorithmically produce the sequence above in $O(N)$ time with $O(1)$ memory as one does not even have to store the sieve (i.e., the sequence $a_1,a_2,ldots$ can be generated on the fly).
The maximum term in the sequence is of size $O(N)$ with a constant small enough (by a great margin) to satisfy the constraints of the problem statement. The sequence could be made much longer without increasing the maximum term (e.g., we could use $12a_1,20a_2,45a_1$ as additional triple); I suspect that the maximum term can be made $O(sqrt N)$.
answered Jan 6 at 18:28
Hagen von EitzenHagen von Eitzen
278k22269497
edited Jan 6 at 21:48
answered Jan 6 at 18:28
Hagen von EitzenHagen von Eitzen
278k22269497
answered Jan 6 at 18:28
Hagen von EitzenHagen von Eitzen
278k22269497
answered Jan 6 at 18:28
Hagen von EitzenHagen von Eitzen
278k22269497
278k22269497
$begingroup$
suppose N=4 Sequence would be: 6,10,15,14 but gcd(14,6,10) is not 1. Any way to solve this out?
$endgroup$
– Rizwan Ansari
Jan 6 at 18:46
$begingroup$
Why should it matter that $gcd(14,6,10)>1$? These are not three consecutive terms
$endgroup$
– Hagen von Eitzen
Jan 6 at 18:51
$begingroup$
If my question wasn't clear : Ai , A(i+1) mod N, A(i+2) mod N are adjacent to each other
$endgroup$
– Rizwan Ansari
Jan 6 at 18:54
$begingroup$
@RizwanAnsariOops, I overread that condition. Will adjust quickly
$endgroup$
– Hagen von Eitzen
Jan 6 at 18:56
$begingroup$
for N=6, Sequence: 6,10,15,12,30,75 but gcd(15,12,30) isn't 1. Fails without cycle as well :/
$endgroup$
– Rizwan Ansari
Jan 6 at 19:25
|
show 2 more comments
$begingroup$
suppose N=4 Sequence would be: 6,10,15,14 but gcd(14,6,10) is not 1. Any way to solve this out?
$endgroup$
– Rizwan Ansari
Jan 6 at 18:46
$begingroup$
Why should it matter that $gcd(14,6,10)>1$? These are not three consecutive terms
$endgroup$
– Hagen von Eitzen
Jan 6 at 18:51
$begingroup$
If my question wasn't clear : Ai , A(i+1) mod N, A(i+2) mod N are adjacent to each other
$endgroup$
– Rizwan Ansari
Jan 6 at 18:54
$begingroup$
@RizwanAnsariOops, I overread that condition. Will adjust quickly
$endgroup$
– Hagen von Eitzen
Jan 6 at 18:56
$begingroup$
for N=6, Sequence: 6,10,15,12,30,75 but gcd(15,12,30) isn't 1. Fails without cycle as well :/
$endgroup$
– Rizwan Ansari
Jan 6 at 19:25
$begingroup$
suppose N=4 Sequence would be: 6,10,15,14 but gcd(14,6,10) is not 1. Any way to solve this out?
$endgroup$
– Rizwan Ansari
Jan 6 at 18:46
$begingroup$
suppose N=4 Sequence would be: 6,10,15,14 but gcd(14,6,10) is not 1. Any way to solve this out?
$endgroup$
– Rizwan Ansari
Jan 6 at 18:46
$begingroup$
Why should it matter that $gcd(14,6,10)>1$? These are not three consecutive terms
$endgroup$
– Hagen von Eitzen
Jan 6 at 18:51
$begingroup$
Why should it matter that $gcd(14,6,10)>1$? These are not three consecutive terms
$endgroup$
– Hagen von Eitzen
Jan 6 at 18:51
$begingroup$
If my question wasn't clear : Ai , A(i+1) mod N, A(i+2) mod N are adjacent to each other
$endgroup$
– Rizwan Ansari
Jan 6 at 18:54
$begingroup$
If my question wasn't clear : Ai , A(i+1) mod N, A(i+2) mod N are adjacent to each other
$endgroup$
– Rizwan Ansari
Jan 6 at 18:54
$begingroup$
@RizwanAnsariOops, I overread that condition. Will adjust quickly
$endgroup$
– Hagen von Eitzen
Jan 6 at 18:56
$begingroup$
@RizwanAnsariOops, I overread that condition. Will adjust quickly
$endgroup$
– Hagen von Eitzen
Jan 6 at 18:56
$begingroup$
for N=6, Sequence: 6,10,15,12,30,75 but gcd(15,12,30) isn't 1. Fails without cycle as well :/
$endgroup$
– Rizwan Ansari
Jan 6 at 19:25
$begingroup$
for N=6, Sequence: 6,10,15,12,30,75 but gcd(15,12,30) isn't 1. Fails without cycle as well :/
$endgroup$
– Rizwan Ansari
Jan 6 at 19:25
|
show 2 more comments
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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%2f3064225%2fsequence-of-n-numbers%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
