1
$\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:

  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?

$\endgroup$
2
$\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.

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

$\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.