YET ANOTHER ALGORITHM FOR SEARCH NUMBERS WITH MAXIMAL QUANTITY OF DIVISORS (BASED ON IDEA OF NON-DOMINATED PAIRS SET)

Abstract

Introduction. This article is essentially a continuation of the article [6]. It considers almost the same formulation of the problem (search for number with maximal quantity of divisors among all numbers in given interval, but this time only from 1 to given N, and it’s necessary to find minimal of the numbers which have the maximal quantity of divisors). Despite similar formulation, a fundamentally different way of solving is proposed. It’s based on the introduced concept of non-dominated pairs, namely: a pair (number, quantity of its divisors) is considered non-dominated iff there are no smaller numbers that have greater or equal quantity of divisors. Similarly to [6], this article considers generalization when maximum quantity of divisors is sought not among all numbers in the interval, but only among non-multiples of some K (natural, greater than or equal to 2, not necessarily prime).
Purpose. The purpose of the article is to describe the designed algorithm for solving problem of searching numbers with maximal quantity of divisors, based on sets of non-dominated pairs, and its variations. Similarly to [6], several problem formulation versions are considered:
1. Given a positive integer N, for all integers in range between 1 and N (both inclusive), find number having maximal (among numbers in the range) quantity of divisors.
3. Given positive integers N and K (K ≥ 2), for integers in range between 1 and N (both inclusive), but excluding multiples of K, find number having maximal (among the said numbers) quantity of divisors.
Results and conclusion. After introducing definitions “pair (v, τ(v)) is non-dominated under constraints … (where … is replaced with some constraints) iff it satisfies the constraints and there is no satisfying the constraints pair (w, τ(w)) where w < v and τ(w) ≥ τ(v)” and “S(N, j) is set of all pairs (v, τ(v)), non-dominated under constraints v ≤ N and factorization of v contains non-zero degrees for p0 = 2, p1 = 3, …, pj”, an inductive algorithm building S(N, 0), S(N, 1), … is proposed and proved; theoretical and practical estimate for such j* that S(N, j*) = S(N, j*+1) = … = S(N, ∞) are proposed and proved. Algorithm finding high composite numbers using S(N, 0), S(N, 1), … is implemented. Comparing this algorithm with same-goal algorithm from [6], new one found to be much faster to build all highly-composite numbers in range 1..N, than algorithm from [6] to find maximal only.
Modification for task formulation 3 is based on introducing new series of sets R(N, j, K) which are sets of all pairs (v, τ(v)), non-dominated under constraints v ≤ N and factorization of v contains non-zero degrees for p0 = 2, p1 = 3, …, pj, and (what differs R(N, j, K) from S(N, j)) v can’t become a multiple of K after multiplying with any product of any powers of pj+1, pj+2, …. Inductive algorithm building S(N, 0), R(N, 0, K), S(N, 1), R(N, 0, K), … is proposed and proved; theoretical and practical estimate for finishing the process are proposed and proved. This algorithm solves problem in formulation 3, consuming amounts of time and memory, comparable to algorithm for formulation 1.