Mutually prime numbers

This example examines the implementation of the Julia search algorithm for Coprimes, which filters sets of numbers, leaving only those where all numbers are coprimes (their NODE is 1).

Introduction

The algorithm for searching for mutually prime sets of numbers solves the problem of filtering sets of numbers, leaving only those in which all numbers are mutually prime. Mutually prime numbers are numbers whose greatest common divisor (GCD) is 1. Such sets of numbers are used in cryptography, number theory, and algorithms related to fractions and modular arithmetic.

The main part

Data preparation

First, we define a list of sets of numbers that we will check for mutual primality. Each sublist is a set of numbers, the nodes of which we want to check.

# Source data: a list of sets of numbers
data = [[21,15],[17,23],[36,12],[18,29],[60,15],[21,22,25,31,143]]

6-element Vector{Vector{Int64}}:
 [21, 15]
 [17, 23]
 [36, 12]
 [18, 29]
 [60, 15]
 [21, 22, 25, 31, 143]

Now let's apply filtering to this data. To do this, use the function filter, which will leave only those sets for which the condition is met: the largest common divisor of all numbers in the set is 1.

# Filtering: we leave only sets where the NODE of all numbers is 1
# p is a single set of numbers (for example, [21, 15])
# gcd(p...) — calculates the NODE of all numbers in a set, expanding it through "splat" (...)

coprime_sets = filter(p -> gcd(p...) == 1, data)

3-element Vector{Vector{Int64}}:
 [17, 23]
 [18, 29]
 [21, 22, 25, 31, 143]

Let's analyze the expression gcd(p...) more detailed:

p — this is an array of numbers, for example, [21, 15].
p... — this is the "splat" operator, which expands the array into separate arguments. That is gcd([21, 15]...) turns into gcd(21, 15).
gcd — Julia's standard function that calculates the greatest common divisor.

The result of the work

As a result of the algorithm, we get a list of only those sets of numbers in which all the numbers are coprime. Mutual simplicity means that the NODE of all the numbers in the set is 1.

# Output of the result
println("Mutually simple sets:")
for set in coprime_sets
    println(set)
end

Взаимно простые наборы:
[17, 23]
[18, 29]
[21, 22, 25, 31, 143]

Conclusion

In this example, we implemented an algorithm for searching for mutually prime sets of numbers, which filters sets of numbers, leaving only those where all numbers are mutually prime. This is useful in tasks where it is important that numbers do not have common divisors, for example, in cryptography or when working with fractions. We used Julia's built-in functions: filter, gcd and the operator ... to unpack the arguments.

The example was developed using materials from Rosetta Code