Mutually simple triples

This example demonstrates the implementation of an algorithm for finding mutually prime triples in the Julia programming language, which collects a sequence of numbers where every three consecutive numbers are mutually prime.

Introduction

The algorithm for finding infinitely simple triples builds a sequence of natural numbers such that every three consecutive numbers in it are pairwise mutually prime. That is, for any number in sequence, the numbers , and they must be such that any two of them have no common divisors except 1.

This algorithm is interesting in the context of number theory and can be used in problems related to generating sequences with certain divisibility properties.

This code implements a function that builds such a sequence, adding at each step the smallest possible natural number that is not yet part of the sequence and is mutually prime with the two previous numbers.

The main part

Declaring the function coprime_triplets with the parameter less_than the default is 50.

function coprime_triplets(less_than = 50)

    # Initial sequence: The first two elements are 1 and 2.
    # These are the initial conditions from which the construction of the sequence begins.
    cpt = [1, 2]

    # An infinite loop is the basic logic of sequencing.
    while true

        # The variable m is a candidate for the next number in the sequence.
        # Initially, we start with 1.
        m = 1

        # As long as candidate m satisfies one of the conditions:
        # - already present in the sequence (m in cpt)
        # - is not mutually simple with the previous number (gcd(m, cpt[end]) != 1)
        # - is not mutually simple with the preceding number (gcd(m, cpt[end - 1]) != 1)
        # we increase m by 1.
        while m in cpt || gcd(m, cpt[end]) != 1 || gcd(m, cpt[end - 1]) != 1
            m += 1
        end

        # If m has reached or exceeded the value of less_than, we terminate the function.
        if m >= less_than
            return cpt
        end

        # If m fits, add it to the sequence.
        push!(cpt, m)
    end
end

coprime_triplets (generic function with 2 methods)

After defining the function, we call it with default parameters (up to 50), and we get a ready sequence. trps.

Calling a function to get a sequence of numbers up to 50.

trps = coprime_triplets();

We output the number of numbers found in the sequence.

println("Found $(length(trps)) mutually simple triples less than 50:")

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

We print all the numbers in a row, 10 numbers per line.

enumerate(trps) — creates pairs (index, value)
foreach — performs an action for each element
rpad(p[2], 3) — alignment of a number in a 3-character wide string
p[1] %10 == 0 ? "\n" : "" — if the element number is a multiple of 10, add a newline

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

Conclusion

In this example, we looked at the implementation of the algorithm for searching for mutually intersecting triples in the Julia language. The algorithm builds a sequence of numbers where every three consecutive numbers are prime in pairs. We have analyzed in detail step by step how the function works, starting with the initial conditions and ending with the construction of a complete sequence.

This approach can be useful in problems related to number theory, the generation of special sequences, as well as for educational purposes to demonstrate work with numbers and their properties.

The example was developed using materials from Rosetta Code