0
$\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$
  • 1
    $\begingroup$ Have you tried a few small examples? $\endgroup$ – Joppy Oct 29 '18 at 6:37
  • 1
    $\begingroup$ Have you tried anything? $\endgroup$ – Parcly Taxel Oct 29 '18 at 7:00
  • $\begingroup$ I tried to place some numbers randomly, but no trial was success, failures do not prove. $\endgroup$ – Hussain-Alqatari Oct 29 '18 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$ – Ivan Neretin Oct 29 '18 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$ – Hussain-Alqatari Oct 29 '18 at 10:36
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$
0
$\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$

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.