Module:Rational: Difference between revisions

← Older edit Newer edit →

@@ Line 325: / Line 325: @@
 				return false
 			end
+		end
+	end
+	return true
+end
+-- check if an integer is highly composite
+function p.is_highly_composite(a)
+	if type(a) == 'number' then
+		a = p.new(a)
+	end
+	if a.nan or a.inf or a.zero then
+		return false
+	end
+	-- negative numbers are not highly composite
+	if a.sign == -1 then
+		return false
+	end
+	-- non-integers are not highly composite
+	for factor, power in pairs(a) do
+		if type(factor) == 'number' then
+			if power < 0 then
+				return false
+			end
+		end
+	end
+	local last_power = 1/0
+	local max_prime = p.max_prime(a)
+	for i = 2, max_prime do
+		if u.is_prime(i) then
+			-- factors must be the first N primes
+			if a[i] == nil then
+				return false
+			end
+			-- powers must form a non-increasing sequence
+			if a[i] > last_power then
+				return false
+			end
+			last_power = a[i]
+		end
+	end
+	-- last_power may be >1 only for 1, 4, 36
+	if last_power > 1 then
+		return p.eq(a, 1) or p.eq(a, 4) or p.eq(a, 36)
+	end
+	-- now we actually check whether it is highly composite
+	local n, _m = p.as_pair(a)
+	local divisors = p.divisors(a)
+	-- FIXME: inefficient; we should iterate factorisations of integers <n directly
+	for i = n - 1, 1, -1 do
+		if p.divisors(i) >= divisors then
+			return false
 		end
 	end