Sets with a Given Least Common Multiple

Let $H(n)$ denote the number of sets of positive integers such that the least common multiple of the integers in the set equals $n$.
E.g.:
The integers in the following ten sets all have a least common multiple of $6$:
$\{2,3\}$, $\{1,2,3\}$, $\{6\}$, $\{1,6\}$, $\{2,6\}$, $\{1,2,6\}$, $\{3,6\}$, $\{1,3,6\}$, $\{2,3,6\}$ and $\{1,2,3,6\}$.
Thus $H(6)=10$.

Let $L(n)$ denote the least common multiple of the numbers $1$ through $n$.
E.g. $L(6)$ is the least common multiple of the numbers $1,2,3,4,5,6$ and $L(6)$ equals $60$.

Let $HL(n)$ denote $H(L(n))$.
You are given $HL(4)=H(12)=44$.

Find $HL(50000)$. Give your answer modulo $10^9$.

First let’s understand how to compute $H(n)$.

When computing the least common multiple (LCM), we only care about the powers of each prime factor in the factorization of $n$, and not the specific integers that these prime powers came from. This is because if we have an integer that includes a specific prime power in its factorization, we must include that power in the LCM. The power of a prime in the LCM is the greatest power of that prime in any of the original numbers. So, any set of integers that produces a given LCM $n$ must consist of integers whose prime factorizations only use the prime powers of $n$ (using each at least once, and excluding all the rest).

For example, the factorization of $6$ is $2^1 \times 3^1$, so each set that produces a LCM of $6$ must include $2^1$ and $3^1$ in some way.

For a given prime power $p^k$ that appears in the prime factorization of $n$, there are $k+1$ choices for how it could appear in one of the numbers in the set (it could be $p^0, p^1, …, p^k$). But since each prime power must appear at least once, subtract one from each of these options, giving $k$ choices. Therefore, to get the number of different sets, multiply together these options for each prime power in the factorization of $n$.

Let’s factorize $n$ as $p₁^{k₁} \times p₂^{k₂} \times … \times pᵢ^{kᵢ}$ so, $H(n) = k₁ \times k₂ \times … \times kᵢ$.

In the case of $HL(n) = H(L(n))$, the prime factorization of $L(n)$ only has prime powers of the primes less than or equal to $n$, and the power of each prime $p$ is the greatest $k$ such that $p^k \leq n$ (since $L(n)$ must be divisible by all numbers less than or equal to $n$, in particular all the powers $p^k \leq n$).

For each prime $p \leq n$, this power $k$ is $\lfloor \log_p(n) \rfloor$. Therefore, by the above argument: $HL(n) = \prod_{p ≤ n} \lfloor \log_p(n) \rfloor$ (where $p$ ranges over all primes less than or equal to $n$).

Unfortunately, even with this formula, calculating $HL(50000)$ directly would involve a product of over 5000 terms (one for each prime less than or equal to 50000), which is impractical.

So we use the fact that multiplication is associative, and split the product into groups of approximately equal size (to distribute the calculation as evenly as possible), taking the result modulo $10^9$ in each step to prevent overflow.

Here is a Python script that can be used to calculate this:

“`python
import sympy

def HL(n):
primes = list(sympy.primerange(1, n+1))
prod = 1
for p in primes:
prod *= int(n / p)
prod %= 10**9
return prod

print(HL(50000))
“`

Note: This script uses the SymPy library to find all the prime numbers less than or equal to $n$ (using the primerange function). The key step is calculating $\lfloor \log_p(n) \rfloor$ as int($n/p$) in the for loop, which is equivalent because we are dealing with positive integers $n$ and $p≤n$. The product over all primes is computed in prod. The result is taken modulo $10^9$ in every step with prod %= 10**9.

More Answers: