04.04.2026 13:50
hollz69 16 9200 Источник

Вопрос читателю: Как можно сгруппировать натуральный ряд {1, 2, 3, ..., n} в n / 2 групп, чтобы внутри каждой лежали только взаимно-простые числа?

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

Предыстория

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

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

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

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

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

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

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

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

Сам способ

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

  • В первой группе - 1 и простые числа.

  • Во всех группах после первой в первой строке находятся четные числа.

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

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

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

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

Комментарии (16)


  1. Alexandroppolus
    04.04.2026 15:52
    #29776176

    Разбиение ряда на группы - прикольная тема. Я вот что вспомнил: как разбить весь натуральный ряд (все целые больше 0) на 6 групп, так чтобы для любого k, числа k, 2k, 3k, 4k, 5k и 6k попадали в разные группы. Там тоже простое изящное решение в духе статьи.


    1. hollz69 Автор
      04.04.2026 15:52
      #29776620

      Спасибо, посижу подумаю


    1. wataru
      04.04.2026 15:52
      #29779612

      Для числа k, выделим все степени 7: k = 7^m*b, b % 7 != 1. Положим число в группу b % 7 (от 1 до 6).

      При умножении на 1-6 максимальная степень 7 в числе останется m. Поэтому x*k (1 <= x <= 6) пойдет в группу (x*b)%7. при чем b%7 != 0, x%7 != 0. Все 6 чисел будут разными, потому что таблица умножения ненулевых чисел по модулю 7 имеет перестановки в каждой строке или столбце. Это потому что умножение по модулю 7 обратимо, ведь 7 - простое число.

      Это можно заметить, если руками распихать первые 6 чисел и ими порожденные числа. Там почти однозначно числа распределяются по модулю 7. И тогда остается вопрос, что делать с числами, делящимеся на 7.


      1. Alexandroppolus
        04.04.2026 15:52
        #29779734

        И тогда остается вопрос, что делать с числами, делящимеся на 7

        Да, этот момент всё портит) Пока не уверен, что здесь можно пофиксить.

        Моё решение немного другое


        1. wataru
          04.04.2026 15:52
          #29779748

          Нет, понятно же. Поделить на 7, пока делится. Я тут имел ввиду, что я не знаю, как я до этого додумался.


          1. Alexandroppolus
            04.04.2026 15:52
            #29779836

            А, понял. Да, согласен, решение рабочее. Можно ли его обобщить на N групп (по которым распределяются числа k, 2k, ..., N*k)?

            Мой вариант для 6 групп: определяем в числе степени множителей 2, 3 и 5, пусть это будут a, b, c. Тогда число попадает в группу (a + 3b + 5c) % 6. Для N групп надо рассматривать степени всех простых множителей меньше N, но не совсем понятно, как подобрать коэффициенты для суммы..


            1. wataru
              04.04.2026 15:52
              #29780186

              Можно ли его обобщить на N групп (по которым распределяются числа k, 2k, ..., N*k)?

              Если N+1 простое - мой метод работает как есть.

              Для непростых N+1 - уже нет. Но не факт что такие разбиения вообще всегда существуют. Хотя я контрпримеров пока не нашел.

              определяем в числе степени множителей 2, 3 и 5,

              Вообще, логично. Все множители 1..N только меняют степени у этих чисел, поэтому числа с разными другими простыми множителями никогда и никак не получатся вместе, а значит у нас бесконечно идентичных компонент связности в графе конфликтов. Если мы как-то расположим только числа с этими простыми делителями. мы можем скопировать это решение на все оставшиеся компоненты. Кстати, это еще показывает, что решений бесконечно много, если они есть, даже без учета перестановок N групп. Можно брать разную перестановку в каждой отдельной компоненте связности.


  1. celen
    04.04.2026 15:52
    #29776788

    (1,2),(3,4),(5,6)… ?


    1. hollz69 Автор
      04.04.2026 15:52
      #29776938

      Я нашел нестандартный способ решения задачи.


      1. celen
        04.04.2026 15:52
        #29778784

        Искусство мысли учит нас, что некоторые задачи имеют много решений, одно из которых - лучшее. Обычно «лучшее» обозначает «самое простое по конструкции».

        Решенная вами задача объективно примитивна. Любой матшкольник с минимальным опытом теории чисел с легкостью придумает десятки конструкций типа вашей. Во всех них в каждой группе будет по одному четному числу, а нечетные могут быть разложены по разнообразным принципам, потому что число степеней свободы разложить эти числа по группам очень велико комбинаторно. Я думаю, что если вы будете раскладывать случайно, после чего возьмете неподходящие и переложите их и так будете повторять несколько итераций, то все равно быстро подберете подходящую конфигурацию.

        Ваша задача имеет околонулевную сложность решения.

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

        Хотите настоящий вызов? Представьте, что на условие наложено дополнительное требование: числа в группе должны быть не только взаимопростыми, но еще и иметь минимальную попарную разность по модулю не меньше чем d. Вопрос: при каком максимальном d существует решение при такой постановке?


        1. Alexandroppolus
          04.04.2026 15:52
          #29779100

          Вопрос: при каком максимальном d существует решение при такой постановке?

          Любопытный апгрейд. Разбивку 2n чисел можно сделать, если d равен наибольшему нечетному простому числу, которое меньше чем n. Тогда каждому четному можно подобрать пару в виде нечетного. Причем если вышло так, что d = n-1, то больше точно нельзя (тривиально доказывается). Но вот всегда ли это максимум, не совсем понятно...


  1. Sirion
    04.04.2026 15:52
    #29777246

    Это лажовый способ по двум причинам. Во-первых, в нём нет ничего интересного, кроме синдрома NIH. Во-вторых, что более важно, он не обобщается на произвольное n. Например, всё ломается при n=1000. Простых чисел меньше тысячи всего 168. Второе число может быть только в группах с номерами не больше 250. Итого всего по группам распределяется не более 500 + 250 + 168 чисел, что, очевидно, меньше 1000.

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


    1. hollz69 Автор
      04.04.2026 15:52
      #29778140

      Я вот сейчас понял, что в одной колонке может быть и два нечетных составных числа, т.к \lfloor x/4 + 0.5 \rfloor может давать одинаковый результат для нескольких чисел: например \lfloor55/4 + 0.5\rfloor=14=\lfloor 57/4+0.5\rfloor. В таком случае никакого ограничения на 250 чисел нет.

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


      1. Sirion
        04.04.2026 15:52
        #29778188

        А теперь скажите, есть ли смысл делить нечётные числа на простые и составные?


        1. hollz69 Автор
          04.04.2026 15:52
          #29778212

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


          1. Sirion
            04.04.2026 15:52
            #29779628

            Да, в том числе на это. Но вообще тут много вариантов. Простые числа можно, например, закидывать в любую группу, где максимальное число не более чем в два раза больше этого простого. Можно менять местами числа вида 2n и 4n. Можно производить много всякой суеты. Но всё это не демонстрирует никаких глубинных идей. Это просто раскладывание математического пасьянса. А раскладывание пасьянса интересно только раскладывающему.