# Positive integers around a circle

I found this question in a number theory book, I could not answer it, any help please;

Is it possible to place 1005 distinct positive integers around a circle so that for any two adjacent numbers, the ratio of the greater to the smaller is a prime number?

What if the integer 1005 is replaced with any other positive integer?

• Have you tried a few small examples? – Joppy Oct 29 '18 at 6:37
• Have you tried anything? – Parcly Taxel Oct 29 '18 at 7:00
• I tried to place some numbers randomly, but no trial was success, failures do not prove. – Hussain-Alqatari Oct 29 '18 at 8:10
• Look, I did place some numbers randomly: 2,6,3,15,5,10. Pity there are only six of them, and not 1005. But still, maybe this would spark any ideas? – Ivan Neretin Oct 29 '18 at 8:20
• Ivan Neretin, yes, your number satisfies the condition that for any two adjacent numbers, the ratio of the greater to the smaller is a prime number. However, giving an example does not prove for larger values such as 1005. – Hussain-Alqatari Oct 29 '18 at 10:36

If the numbers $$a_1,a_2,\ldots,a_n$$ are placed in a circle, and if $$r_i=a_{i+1}/a_i$$, with $$a_{n+1}=a_1$$, then $$r_1r_2\cdots r_n=1$$. Now if each $$r_i$$ is either a prime or the reciprocal of a prime, then for each $$r_i$$ that is a prime there must be a corresponding $$r_j$$ that is the reciprocal of that prime. (More precisely, for each prime $$p$$, the number of indices for which $$r_i=p$$ must equal the number of indices for which $$r_i=1/p$$.) But this can only happen if $$n$$ is even. Since $$1005$$ is odd, it is not possible to place $$1005$$ integers in a circle so that for each pair of adjacent numbers the ratio of the larger to the smaller is prime.

Note, this argument is unconcerned with the condition that the $$a_i$$'s be distinct; that is, if $$n$$ is odd, there's no arrangement of numbers with prime ratios even if numbers are allowed to repeat. For $$n=2m$$, on the other hand, we can get distinct numbers by taking $$p_1,p_2,\ldots,p_{m-1}$$ to be distinct primes (say the first $$m-1$$ primes) and then letting

\begin{align} a_1&=1\\ a_{i+1}&=a_ip_i\quad\text{for }1\le i\le m-1\\ a_{i+1}&=a_i/p_{i-m+1}\quad\text{for }m\le i\le2m-1 \end{align}

e.g., $$(a_1,\ldots,a_8)=(1,2,6,30,210,105,35,7)$$.

HINT.-Let $$\{n_k\}_{1\le k\le2005}$$ be the sequence. The answer is NO. We can see it for example for simple sequences of three or five numbers instead of $$2005$$ ones exhausting all the possibilities. There would be no difficulty, however, if we excluded the ratio of the greater to the smaller for two "consecutive" numbers $$n_k$$ and $$n_ {k + 1}$$ particularly for $$n_1$$ and $$n_{2005}$$.

Example 1.- $$n_1=p_1$$, $$n_2=p_1p_2$$ and so on $$n_k=p_1p_2\cdots p_k$$ where the factors $$p_i$$ are distinct primes. In this case we exclude the comparison between the adjacent $$n_1$$ and $$n_{2005}$$

Example 2.-$$\begin{cases}n_1=p_1,\space\space n_2=p_1p_2,\space\space n_3=p_1p_2p_4,\cdots\\n_{2005}=p_1p_3,\space\space n_{2004}=p_1p_3p_5,\cdots\end{cases}$$

In this case we exclude comparison between two adjacent $$n_k$$ and $$n_{k+1}$$ for $$3\le k\le 2004$$, particularly (in order to follow some "symmetry" in the construction of the sequence) we can choose $$k=2003$$.