Module:JI ratios: Difference between revisions

← Older edit Newer edit →

@@ Line 39: / Line 39: @@
 --------------------------------------------------------------------------------
----------------------------- RATIO SEARCH FUNCTIONS ----------------------------
+----------------------- INT-LIMIT-BASED SEARCH FUNCTION ------------------------
 --------------------------------------------------------------------------------
@@ Line 91: / Line 91: @@
 	return ratios
 end
+--------------------------------------------------------------------------------
+------------------------ SUBGROUP-BASED SEARCH FUNCTION ------------------------
+--------------------------------------------------------------------------------
+-- Requires helper functions
+function p.search_by_subgroup(subgroup, int_limit, max_cents)
+	local subgroup = subgroup or { 2, 3, 7, 11 }
+	local int_limit = int_limit or 50
+	local max_cents = max_cents or 1200
+end
+-- Helper function
+-- Given a set of factors and a max product, find all values up to the max
+-- product that is divisible by at least one of those primes.
+-- Factors are either prime or coprime, thus handling nonprime subgroups.
+function p.find_products(factors, max_product)
+	local factors = factors or { 2, 3, 7, 11 }
+	local max_product = max_product or 100
+	local products = {  }
+	-- A naive approach is to iterate through all numbers 2..max_product and in-
+	-- sert them in a table if it consists of at least one of the given factors.
+	-- Using these numbers, make every possible pair from these numbers to
+	-- produce a table of ratios within the desired subgroup, given the factors
+	-- represent a subgroup. This is super inefficient as just the process of
+	-- producing products involves checking numbers that are produced by factors
+	-- outside the set of desired factors, which is the vast majority of num-
+	-- bers. A more targeted approach is to do the following:
+	-- - For each factor fi, calculate the largest power pi of that factor that
+	--   is just less than the max product. Keep track of these powers as a
+	--   vector of powers.
+	-- - For factors f1, f2, ... fn, and powers p1, p2, ... pn, represent the
+	--   potential powers as sets {0,1,...,p1}, {0,1,...,p2}, ..., {0,1,...,pn}.
+	--   The set of all possible vectors of powers is the cartesian product of
+	--   these sets.
+	-- - These vectors encode prime factorizations, and to reduce the quantity
+	--   of products, only permit products that are less than that of the max
+	--   product. Additionally, since these encode prime factorizations, the use
+	--   of negative exponents produces ratios for free!
+	-- - NOTE ABOUT VECTORS OF POWERS: these vectors may be thought of as monzos
+	--   but without the potential sparseness. EG, whereas [2 0 0 1 1> is a
+	--   shorthand for 308, in the context of the 2.7.11 subgroup, the lack of
+	--   3's and 5's makes the inclusion of these zeroes wasteful; hence the
+	--   factors are denoted as a vector {2,7,11} and the powers {2,1,1}.
+	--   Another way to think of these vectors is as a number where each
+	--   position is a different base; thus, producing every possible vector is
+	--   as simple as counting up, which is how these vectors are produced in
+	--   code.
+	local max_powers = {}
+	local curr_powers = {}
+	for i = 1, #factors do
+		local curr_factor = factors[i]
+		local curr_max_multiplier = math.floor(max_product/curr_factor)
+		local max_power = math.log(max_product) / math.log(curr_factor)
+		table.insert(max_powers, math.floor(max_power))
+		table.insert(curr_powers, 0)
+	end
+	-- Increment current powers one by one
+	while curr_powers[#curr_powers] < max_powers[#max_powers] do
+		curr_powers[1] = curr_powers[1] + 1
+		for i = 1, #factors - 1 do
+			if curr_powers[i] > max_powers[i] then
+				curr_powers[i] = 0
+				curr_powers[i+1] = curr_powers[i+1] + 1
+			end
+		end
+		local curr_product = 1
+		for i = 1, #curr_powers do
+			curr_product = curr_product * math.pow(factors[i], curr_powers[i])
+		end
+		if curr_product <= max_product then
+			table.insert(products, curr_product)
+		end
+	end
+	table.sort(products)
+	return max_powers
+end
+-- Check whether a number is composed of the following factors.
+function p.is_divisible_by_factors(number, factors)
+	local test_number = number
+	for i = 1, #factors do
+		local is_divisible = true
+		while test_number ~= 0 and is_divisible do
+			is_divisible = false
+			if test_number % factors[i] == 0 then
+				test_number = test_number / factors[i]
+				is_divisible = true
+			end
+		end
+	end
+	return test_number == 1
+end
+--------------------------------------------------------------------------------
+------------------------- PARAM-BASED SEARCH FUNCTIONS -------------------------
+--------------------------------------------------------------------------------
 -- Search for ratios based on params passed in. Each param is its own
@@ Line 278: / Line 388: @@
 	--return p.ratios_as_text(ratios) .. " " .. #ratios
-	return p.search_by_params(params)
+	-- Using these params with the naive search algorithm takes several seconds
+	-- to return only 1563 results: factors 2, 3, 7, 11; max product: 10 million
+	local factors = { 2, 3, 7, 11 }
+	local max_product = 20
+	return p.find_products(factors, max_product)
 end
 return p