1
$\begingroup$

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?

$\endgroup$
6
  • 1
    $\begingroup$ Have you tried a few small examples? $\endgroup$
    – Joppy
    Commented Oct 29, 2018 at 6:37
  • 1
    $\begingroup$ Have you tried anything? $\endgroup$ Commented Oct 29, 2018 at 7:00
  • $\begingroup$ I tried to place some numbers randomly, but no trial was success, failures do not prove. $\endgroup$ Commented Oct 29, 2018 at 8:10
  • 1
    $\begingroup$ 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? $\endgroup$ Commented Oct 29, 2018 at 8:20
  • $\begingroup$ 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. $\endgroup$ Commented Oct 29, 2018 at 10:36

2 Answers 2

1
$\begingroup$

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

$\endgroup$
-1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .