Наименьшее количество различных чисел во множестве

[Ktina]

Натуральные числа

$$n_1, n_2, \dots , n_{2018}$$

таковы, что числа

$$\dfrac{n_1}{n_2}, \dfrac{n_2}{n_3},\dots , \dfrac{n_{2017}}{n_{2018}}$$

попарно различны.

Найдите наименьшее количество различных чисел во множестве

$$\{n_1, n_2,\dots , n_{2018}\}$$

[atlakatl]

32 попарно некратных чисел образуют $32 \cdot 31=992$ дроби и столько же обратных им. Получаем 1984 различных числа, да ещё одно, равное единице. Оставшиеся $2018-1985=33$ числа формируются - с запасом - тоже 33-м числом. Это и есть ответ.
Сейчас понял, что решал не ту задачу. Ведь числа составляют только пары? И дальше никак не используются?
Нет, всё верно. 33.
Например, первые 33 простые:
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
101
103
107
109
113
127
131
137
образуют $2/2, 2/3, 3/2, 2/5, 5/2, ..., 131/137, 137/131$ - все разные.

[gris]

Боюсь, что обратные уже входят в эти 992 дроби. То есть нужно всё же 46 чисел, чтобы из них сформировать 2070 пар с различными отношениями. Но надо показать, что их можно выстроить.

[Ktina]

gris в сообщении #1290218 писал(а):

Но надо показать, что их можно выстроить.

Вот в этом-то и...

[gris]

Если взять идею atlakatl для длины желанной последовательности $14$, то можно видеть, что $4\cdot3+1=13=14-1$ как раз подходит. То есть достаточно 4-х чисел. Возьмём $1,2,3,5$. Из них можно сформировать 12 пар с различными отношениями плюс одна пара из каких-нибудь одинаковых чисел. С неё можно и начать: $11$. А дальше приставляем числа, чтобы пары не повторялись. Главное, не угодить в ситуацию, когда приставлять нечего. Но алгоритм достаточно прост. Например, вот такая последовательность:
$11235321315251$.

[atlakatl]

gris в сообщении #1290218 писал(а):

надо показать, что их можно выстроить.

Доказать, что частное разных простых не может быть равным, можно, исходя из технологии перевода периодической десятичной дроби в обычную. Одинаковый период даёт однозначную дробь, которая никакими богами не может получится из несократимых дробей.

[gris]

Я имел в виду "выстроить в последовательность". Например, в приведённом мной примере некто может начать выстраивать так: "11213151..." по алгоритму: начавши с единицы за очередным числом ставим наименьшее из чисел, которое ещё не использовалось в паре с ним" и прийти к невозможности продолжения.