Type-Level Least Common Multiple (LCM) in TypeScript

This challenge involves implementing the Least Common Multiple (LCM) function at the type level in TypeScript. This means we will be working with types and their relationships rather than runtime values. Type-level programming can be incredibly powerful for enforcing constraints and performing computations at compile time, leading to more robust and predictable code.

Problem Description

Your task is to create a TypeScript type LCM<A, B> that computes the Least Common Multiple of two positive integer literal types A and B. The LCM of two integers is the smallest positive integer that is a multiple of both.

To achieve this, you will likely need to implement helper types to:

1. Check for divisibility: Determine if one type-level integer is divisible by another.
2. Find the Greatest Common Divisor (GCD): The GCD is a crucial component in efficiently calculating the LCM, as LCM(A, B) = (A * B) / GCD(A, B).
3. Handle iteration or recursion: To find the smallest common multiple, you might need a way to generate multiples or iterate until a condition is met.

The final LCM<A, B> type should correctly infer the LCM for any two positive integer literal types.

Examples

Example 1:

type Result1 = LCM<3, 5>;
// Expected: type Result1 = 15

Explanation: The smallest positive integer divisible by both 3 and 5 is 15.

Example 2:

type Result2 = LCM<12, 18>;
// Expected: type Result2 = 36

Explanation: Multiples of 12: 12, 24, 36, 48, ... Multiples of 18: 18, 36, 54, ... The smallest common multiple is 36.

Example 3:

type Result3 = LCM<7, 7>;
// Expected: type Result3 = 7

Explanation: The LCM of a number with itself is the number itself.

Example 4: (Edge Case)

type Result4 = LCM<1, 10>;
// Expected: type Result4 = 10

Explanation: Any positive integer is a multiple of 1.

Constraints

• A and B will always be positive integer literal types (e.g., 1, 5, 100).
• The maximum value of A and B will not exceed 1000 to prevent excessive compilation times.
• The resulting LCM will also not exceed 10000.
• You may assume A and B are greater than or equal to 1.

Notes

• TypeScript's type system is powerful but has limitations. You'll be working with template literal types and conditional types.
• You will likely need a type to represent subtraction (Subtract<A, B>), addition (Add<A, B>), and comparison (IsEqual<A, B>, IsLess<A, B>). You can either implement these yourself or use commonly known patterns for type-level arithmetic if you are familiar with them.
• Consider how you will implement the GCD. The Euclidean algorithm is a standard and efficient approach.
• Think about the base cases for any recursive type definitions you might use.
• The goal is a pure type-level solution; no runtime JavaScript code should be required to perform the LCM calculation.