Sequence of N numbers

Question

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?

Answer 1

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.

Answer 2

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)$.