# Sequence of N numbers

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:

1. All numbers are distinct;

2. All numbers lie between $$1$$ to $$10^{19}$$;

3. Two adjacent numbers are NOT co-prime;

4. 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?

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.

• can you give an example with a smaller value of N? – Rizwan Ansari Jan 6 at 19:22
• Efficient way/algorithm to fill my array? – Rizwan Ansari Jan 6 at 20:34
• 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 – Mindlack Jan 6 at 20:36

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 $$N\ge 6$$ in what follows and write $$N=3L+r$$ with $$0\le r\le 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_{k\pm1},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 $$M\ge 16666\cdot \frac 21\cdot \frac 32\cdot \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_{k\pm1}&,&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)$$.

• suppose N=4 Sequence would be: 6,10,15,14 but gcd(14,6,10) is not 1. Any way to solve this out? – Rizwan Ansari Jan 6 at 18:46
• Why should it matter that $\gcd(14,6,10)>1$? These are not three consecutive terms – Hagen von Eitzen Jan 6 at 18:51
• If my question wasn't clear : Ai , A(i+1) mod N, A(i+2) mod N are adjacent to each other – Rizwan Ansari Jan 6 at 18:54
• @RizwanAnsariOops, I overread that condition. Will adjust quickly – Hagen von Eitzen Jan 6 at 18:56
• for N=6, Sequence: 6,10,15,12,30,75 but gcd(15,12,30) isn't 1. Fails without cycle as well :/ – Rizwan Ansari Jan 6 at 19:25