K-Smooth Factorial Numbers
In the realm of distributed systems and resource allocation, unique identifiers and resource scheduling often rely on sequences of numbers with specific mathematical properties. For instance, certain cryptographic protocols or distributed ledger systems might require numbers whose prime factors are constrained to a small set, ensuring predictable computational costs for factorization or modular arithmetic. This problem explores such a sequence, combining concepts of prime factorization and factorials, to identify numbers suitable for specific system-level applications.
Your task is to implement a function findKthSmoothFactorial that determines the N-th positive integer X conforming to the following criteria:
X are less than or equal to a given integer K.X must be a multiple of K! (K factorial).The sequence of such numbers X should be strictly increasing. You need to find the N-th number in this ordered sequence.
Function Signature:
function findKthSmoothFactorial(K: number, N: number): bigint (TypeScript)
function findKthSmoothFactorial(K, N) (JavaScript)
Parameters:
K: A positive integer representing the upper bound for prime factors and the base for the factorial. (2 <= K <= 10)N: A positive integer representing the index of the number to find in the sorted sequence. (1 <= N <= 1000)Return Value:
bigint (TypeScript) or a BigInt (JavaScript) representing the N-th K-Smooth Factorial Number.K! denotes K factorial (e.g., 5! = 5 * 4 * 3 * 2 * 1 = 120).BigInt in JavaScript/TypeScript is necessary for calculations and the return value. Do not use standard number for intermediate or final results that might exceed Number.MAX_SAFE_INTEGER.K=2, the allowed prime factors are just {2}. 2! = 2. The sequence of 2-Smooth Factorial Numbers is 2, 4, 8, 16, ... (i.e., 2^1, 2^2, 2^3, ...).Examples
Example 1
Input:
K = 3, N = 4
Output:
24n
Note:
For K=3, the allowed prime factors are {2, 3}. K! = 3! = 6. Numbers with only prime factors 2 and 3: 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, ... Filtering for multiples of 6: 6, 12, 18, 24, 36, ... The 4th number in this sequence is 24.
Example 2
Input:
K = 2, N = 3
Output:
8n
Note:
For K=2, the allowed prime factors are {2}. K! = 2! = 2. Numbers with only prime factor 2: 1, 2, 4, 8, 16, ... Filtering for multiples of 2: 2, 4, 8, 16, ... (Note: 1 is not a multiple of 2). The 3rd number in this sequence is 8.
Example 3
Input:
K = 5, N = 10
Output:
1440n
Note:
For K=5, the allowed prime factors are {2, 3, 5}. K! = 5! = 120. The problem is equivalent to finding the N-th number X such that X = Y * K!, where Y is a K-smooth number (i.e., Y's prime factors are only from {2,3,5}). The first few K-smooth numbers (for primes {2,3,5}) are: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, ... The 10th such Y is 12. Therefore, the 10th K-Smooth Factorial Number is 12 * 120 = 1440.
Constraints
2 <= K <= 101 <= N <= 1000number type. Use BigInt for all such computations.K or N. A solution with polynomial time complexity in N and K is expected.N and K.K or N being negative, non-integer, or outside specified bounds). Assume valid inputs.BigInt operations.N-th K-Smooth Factorial Number for all valid inputs.K values (e.g., K=2, K=3) and N=1.BigInt to handle values exceeding standard integer limits.Loading editor...