Взаимно простые тройки

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

Введение

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

Этот алгоритм интересен в контексте теории чисел и может использоваться в задачах, связанных с генерацией последовательностей с определёнными свойствами делимости.

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

Основная часть

Объявляем функцию coprime_triplets с параметром less_than по умолчанию 50.

function coprime_triplets(less_than = 50)

    # Начальная последовательность: два первых элемента — это 1 и 2.
    # Это начальные условия, с которых начинается построение последовательности.
    cpt = [1, 2]

    # Бесконечный цикл — основная логика построения последовательности.
    while true

        # Переменная m — кандидат на следующее число в последовательности.
        # Изначально начинаем с 1.
        m = 1

        # Пока кандидат m удовлетворяет одному из условий:
        # - уже есть в последовательности (m in cpt)
        # - не взаимно прост с предыдущим числом (gcd(m, cpt[end]) != 1)
        # - не взаимно прост с предпредыдущим числом (gcd(m, cpt[end - 1]) != 1)
        # увеличиваем m на 1.
        while m in cpt || gcd(m, cpt[end]) != 1 || gcd(m, cpt[end - 1]) != 1
            m += 1
        end

        # Если m достигло или превысило значение less_than, прекращаем работу функции.
        if m >= less_than
            return cpt
        end

        # Если m подходит, добавляем его в последовательность.
        push!(cpt, m)
    end
end

coprime_triplets (generic function with 2 methods)

После определения функции мы вызываем её с параметрами по умолчанию (до 50), и получаем готовую последовательность trps.

Вызов функции для получения последовательности чисел до 50.

trps = coprime_triplets();

Выводим количество найденных чисел в последовательности.

println("Найдено $(length(trps)) взаимно простых троек, меньших 50:")

Найдено 36 взаимно простых троек, меньших 50:

Печатаем все числа в строку, по 10 чисел в строке.

enumerate(trps) — создаёт пары (индекс, значение)
foreach — выполняет действие для каждого элемента
rpad(p[2], 3) — выравнивание числа в строке шириной 3 символа
p[1] %10 == 0 ? "\n" : "" — если номер элемента кратен 10, добавляем перевод строки

foreach(p -> print(rpad(p[2], 3), p[1] % 10 == 0 ? "\n" : ""), enumerate(trps))

Found 36 coprime triplets less than 50:
1  2  3  5  4  7  9  8  11 13 
6  17 19 10 21 23 16 15 29 14 
25 27 22 31 35 12 37 41 18 43 
47 20 33 49 26 45

Заключение

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

Такой подход может быть полезен в задачах, связанных с теорией чисел, генерацией специальных последовательностей, а также в образовательных целях для демонстрации работы с числами и их свойствами.

Пример разработан с использованием материалов Rosetta Code

Взаимно простые тройки