Все целые точки на числовой прямой

[Ktina]

На числовой прямой отмечены все целые точки. Точки $x$ и $y$ соединяются дугой, если $|x-y|$ – простое число, либо произведение двух простых (не обязательно различных). В какое наименьшее количество цветов можно покрасить все целые точки, так чтобы каждые две соединённые точки были разного цвета?
(Фольклор)

[gris]

Попытка. Назовём гвездой n-ного порядка множество из $n$ целых чисел, которые все соединены дугами. Для раскраски гвезды надо $n$ красок. При помещении гвезды в множество других целых чисел, количество требуемых красок не уменьшается.
Примеры: $\{0\},\{0,2\},\{0,2,4\}\{0,2,4,6\}$
Основное свойство гвезды: если ко всем её элементам прибавить одно и то же число, то получим новую гвезду. Поэтому можно гвёзды начинать с нуля.
$\{0,3,5,7,9,14\}$
А вот множество запретных расстояний: $\{1,8,12,15,16,18,20,24,27,28,30...\}$

$\{0,3,5,7,9,22,26\}$ — седьмой порядок. Я думаю, что после этого задача теряет смысл. Семь красок это уже достаточно много. То есть ответ такой, что нужно больше семи красок. Может быть их надо вообще бесконечное количество. Но это уж задача не для меня.
Я вообще решал другую задачу — оценить снизу минимальное количество красок.

Ktina в сообщении #1111695 писал(а):

Напишите хотя бы "UPD", иначе моя реплика кажется непонятной.

Выполняю: UPD.

[Ktina]

gris
Если у Вас ответ 7, то он неверен.

-- 03.04.2016, 10:14 --

gris
Напишите хотя бы "UPD", иначе моя реплика кажется непонятной.

[waxtep]

Ktina в сообщении #1111604 писал(а):

Точки $x$ и $y$ соединяются дугой, если $|x-y|$ – простое число

Получается, двойка будет соединена с бесконечным кол-вом точек?

[grizzly]

waxtep в сообщении #1111760 писал(а):

Получается, двойка будет соединена с бесконечным кол-вом точек?

Получается, что любая точка будет соединена с бесконечным количеством точек. Ну и что? Вы можете покрасить пока число 2 одним цветом, а все остальные другим и продолжить анализ.

[waxtep]

grizzly в сообщении #1111765 писал(а):

все остальные другим и продолжить анализ.

Да, спасибо, это я по невнимательности. У меня получилось пять цветов, попробую сделать рисунок. И даже четыре, если не наврал!

[waxtep]

Нет, снова горячусь уже $\{0,2,3,4,5,6,10,21,25\}$ требует семи цветов, и, кажется, это не предел.

[12d3]

В 8 цветов легко покрасить - разобьем все целые числа на 8 бесконечных арифметических прогрессий с разностью 8 и покрасим каждую в свой цвет.
И раз уж Ktina подсказала, что ответ 7 неверный, значит ответ 8. Осталось доказать.)

[lopkityu]

Как уже сказал 12d3, 8 цветов вполне достаточно, причем не просто сказал, а и указал метод раскраски От себя лишь добавлю, что в наборе $ \{ 0, 2, 4, 6, 9, 11, 13, 15 \} $ все 8 чисел должны быть разных цветов, а значит 7 цветов не хватит.