Ascending primes
In this example, we are implementing an algorithm that finds all prime numbers made up of increasing digits from 1 to 9.
Introduction
The algorithm for searching for increasing primes is designed to find all the primes that can be composed using the numbers from 1 to 9 in ascending order. This means that each subsequent digit in the number is not less than the previous one. This algorithm is used to demonstrate how to work with combinatorics and prime numbers in the Julia programming language. It finds application in mathematical and Olympiad problems where it is required to find certain subsets of numbers.
# Installing the necessary packages
import Pkg; Pkg.add(["Combinatorics", "Primes", "BenchmarkTools"])
# Connecting the necessary libraries
using Combinatorics # For working with combinatorial functions (for example, powerset)
using Primes # To check if a number is prime
using BenchmarkTools # To estimate the execution time
The main part
Function ascendingprimes()
This function generates all possible non-empty subsets of digits from 1 to 9, converts them to numbers, and leaves only prime numbers. Let's look at the work step by step.
# Definition of the ascendingprimes function
function ascendingprimes()
# Generating all possible subsets of a set [1, 2, 3, 4, 5, 6, 7, 8, 9]
# powerset creates all possible combinations of set elements, including an empty set
# We filter the subsets, leaving only the nonempty ones (!isempty(x))
# Then for each subset:
# - reverse(x) expands a subset (for example, [1,2,3] -> [3,2,1])
# - evalpoly(10, reverse(x)) calculates the value of a polynomial with base 10
# This will convert a list of digits to a number (e.g. [1,2,3] -> 321)
# - filter(isprime, ...) leaves only prime numbers
return filter(isprime, [evalpoly(10, reverse(x)) for x in powerset([1, 2, 3, 4, 5, 6, 7, 8, 9]) if !isempty(x)])
end
Conclusion of results
The following code outputs the found primes in formatted form, splitting them into 10 numbers per line.
# Output of all prime numbers in formatted form
# foreach applies a function to each enumeration element
# enumerate adds indexes to the list items
# rpad(p[2], 10) adds spaces on the right so that the number takes up 10 characters.
# p[1] % 10 == 0 ? "\n" : "" - if the index is divisible by 10, a newline is added
foreach(p -> print(rpad(p[2], 10), p[1] % 10 == 0 ? "\n" : ""), enumerate(ascendingprimes()))
Measuring the execution time
The last line measures the execution time of the ascendingprimes() function using the @btime macro.
# Measuring the execution time of the ascendingprimes() function
@btime ascendingprimes()
Conclusion
In this example, we looked at the implementation of the algorithm for searching for increasing primes in the Julia language. We used the Combinatorics package to generate all possible subsets of digits from 1 to 9, as well as the Primes package to check the primality of numbers. We managed to create a function that finds all the prime numbers made up of increasing digits and outputs them in a human-readable format. This example demonstrates the power of the Julia language in mathematical calculations, combinatorics, and working with prime numbers, which can be useful in solving various mathematical problems and algorithmic Olympiads.
The example was developed using materials from Rosetta Code