Consider a sequence $A: a_1, a_2, a_3 .. a_n$ such that each element of this sequence is product of two primes from $p_1, p_2 .. p_m$ so that:

  1. Each $a_i$ is distinct.

  2. $m$ is the least integer so that $\frac{m(m-1)}{2} \ge n$

  3. Any three consecutive elements of sequence are coprime, but any two are not.

For example,

  1. for $n = 3$, we have $m = 3$ and so taking the 3 primes as $a,b,c$, we can say the sequence $A$ is $ab, bc, ac$

  2. For $n = 4$, $m = 4$ and $A: ab, bc, cd, da$

  3. For $n = 6$, $m = 4$ and $A: ab, bd, da, ac, cd, db$

The question is to show that such a sequence exists for any $n$.

If this sequence exists for all $n$, is there a simple pattern for $A$ ?\


There was an error in example 3, no such sequence exists for $n=6$.

  • 1
    $\begingroup$ There is a problem in your example for $n=6$: $bd$ and $db$ are equal. $\endgroup$ – ajotatxe Jan 8 '19 at 15:13
  • $\begingroup$ @ajotatxe sorry I overlooked this one! $\endgroup$ – jeea Jan 8 '19 at 15:23

Your example for $n=6$ doesn't work, because the terms $bd$ and $db$ are the same number, and in fact no valid sequence exists in this case.

This is really a graph theory question: terms of the sequence correspond to edges of the complete graph $K_m$ and the conditions require that two consecutive edges share a vertex but three consecutive edges don't. Equivalently, we are looking for a trail of length $n$. If $m$ is odd there will always be such a trail (because $K_m$ is Eulerian), but if $m$ is even and $n$ is close to the maximum value it won't exist.


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.