Интересный способ сгруппировать натуральный ряд / Хабр

Вопрос читателю: Как можно сгруппировать натуральный ряд в групп, чтобы внутри каждой лежали только взаимно-простые числа?

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

Предыстория

Недавно я открыл для себя книжку Proofs от Jay Cummings и осознал, насколько просто, оказывается, решаются многие красивые задачки, понимая, как правильно составлять в голове их доказательства. Очень советую эту книжку!

Начав решать задачки из первого блока курса, я наткнулся на задачу о доказательстве существования пары взаимно-простых чисел при выборе 31 числа из набора .
Я начал перебирать варианты группировки чисел по 30 группам, опираясь на принцип Дирихле, однако очевидный факт, что соседние числа взаимно-просты, я почему-то игнорировал.

Я лишь заметил, что групп должно быть в два раза меньше, чем самих чисел, а также, что группы должны показывать взаимную простоту чисел внутри.

Набросав варианты, я, неожиданно для себя, нашел такой способ расстановки, что количество групп остается , при $n \in \mathbb{N}$ , и все числа в них взаимно-просты.

Пример таблицы

Попробуйте определить, по какому правилу я составил эти группы? Почему это работает?

{1, 2, 3, ..., 24} — Таблица-демонстрация групп для чисел

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

Сам способ

Очевидно, что все простые числа сразу отправляются в первую группу, а все четные образуют новые группы. Осталось только разобраться с нечетными, составными числами: они расставляются по формуле $pos_{x_i}=\lfloor x_i/4+ 0.5 \rfloor$ . Получается очень красивая таблица, где:

В первой группе - 1 и простые числа.
Во всех группах после первой в первой строке находятся четные числа.
Во всех группах после первой во второй строке находятся нечетные составные числа.
UDP. В таких группах может быть и ноль нечетных чисел (k = 3, k = 7), и два нечетных числа (k = 14, k = 16).

Возможность такого распределения нечетных составных чисел у нас есть благодаря тому, что все такие числа можно представить в виде $4k \pm 1$ (это вроде-как общеизвестный факт), где в моем случае - это номер группы. $gcd(2k, 4k \pm 1)=1$ , т.к. $gcd(4k \pm 1) \equiv \pm1 \pmod{2k}$ , где - это как раз те четные числа.

Вот такой интересный способ распределения натурального ряда я нашел случайно, просто-напросто забыв очевидный факт про соседние числа. Подобное открытие у меня впервые за 10 классов школы.

P.S. Для тренировки можете написать на Python или C++ код, который бы автоматически делал такую разбивку для входного параметра n.