Detailed mathematical approach

Problem Summary

For a positive integer \(n\), let \(H(n)\) be the number of sets of positive integers whose least common multiple is exactly \(n\). The problem then defines

$L(n)=\operatorname{lcm}(1,2,\dots,n),\qquad HL(n)=H(L(n)),$

and asks for \(HL(50000)\bmod 10^9\).

If a set has lcm \(N\), then every element of that set must divide \(N\). So the problem is really about counting subsets of the divisor set of \(N=L(50000)\) whose lcm is exactly \(N\). The challenge is that \(L(50000)\) has many prime factors and an enormous number of divisors, so direct enumeration is completely infeasible.

Mathematical Approach

Write a general target number as

$N=\prod_{i=1}^{k} p_i^{e_i},\qquad d_i=e_i+1.$

Each divisor of \(N\) is determined by choosing, for every prime \(p_i\), an exponent from \(0\) to \(e_i\). Hence \(d_i\) is the number of choices contributed by the \(i\)-th prime.

Step 1: Turn the Problem into a Subset Count

Let \(\mathcal{D}(N)\) be the set of all positive divisors of \(N\). Any valid set is a subset of \(\mathcal{D}(N)\), and because we are counting sets rather than sequences, each divisor is either present or absent exactly once.

For the lcm of a chosen subset to equal \(N\), every prime power \(p_i^{e_i}\) must appear at full strength in at least one selected divisor. In other words, for each prime \(p_i\), at least one chosen divisor must use exponent \(e_i\) at that prime.

Step 2: Apply Inclusion-Exclusion to Force Every Maximal Exponent

For each \(i\), let \(A_i\) be the bad event that no selected divisor reaches exponent \(e_i\) at prime \(p_i\). If a set avoids all bad events, then its lcm is exactly \(N\).

Now choose a subset \(S\subseteq\{1,\dots,k\}\) of primes that are forced to miss their top exponent. For \(i\in S\), a divisor may use only \(0,1,\dots,e_i-1\), so it has \(d_i-1\) choices. For \(i\notin S\), it still has all \(d_i\) choices. Therefore the number of divisors compatible with these restrictions is

$M(S)=\prod_{i\in S}(d_i-1)\prod_{i\notin S}d_i.$

Any subset of those \(M(S)\) divisors satisfies all restrictions in \(S\), so there are \(2^{M(S)}\) such subsets. Inclusion-exclusion gives

$\boxed{H(N)=\sum_{S\subseteq\{1,\dots,k\}}(-1)^{|S|}2^{M(S)}.}$

The empty subset is harmless here: it lies in every bad event, so inclusion-exclusion cancels it automatically.

Step 3: Specialize to \(L(n)\) and Group Equal Local Factors

For \(N=L(n)\), the exponent of a prime \(p\le n\) is

$e_p=\max\{a\ge 0 : p^a\le n\},$

so

$d_p=e_p+1.$

Many primes have the same \(d_p\). That matters because the formula above depends on a prime only through \(d_p\). Suppose one particular value \(d\) occurs for exactly \(c\) primes. If exactly \(i\) of those \(c\) primes belong to \(S\), then:

$(-1)^i\binom{c}{i}$

is the signed combinatorial coefficient, and

$(d-1)^i d^{\,c-i}$

is the factor contributed to \(M(S)\).

If the distinct \(d\)-values are \(d_1,\dots,d_t\) with multiplicities \(c_1,\dots,c_t\), then the subset sum collapses to

$\boxed{HL(n)=\sum_{0\le i_j\le c_j}\left(\prod_{j=1}^{t}(-1)^{i_j}\binom{c_j}{i_j}\right)\,2^{\prod_{j=1}^{t}(d_j-1)^{i_j}d_j^{\,c_j-i_j}}.}$

This is the key reduction: the naive formula has one binary decision per prime, while the grouped formula has only one integer choice per distinct \(d\)-value. Since \(d_p=e_p+1\) and \(e_p\le \lfloor \log_2 n\rfloor\), the number of groups is only \(O(\log n)\).

Step 4: Reduce Huge Powers of Two Modulo \(10^9\)

The exponent

$E=\prod_{j=1}^{t}(d_j-1)^{i_j}d_j^{\,c_j-i_j}$

is enormous, so the implementation never stores it exactly. Instead it only stores the information needed to evaluate \(2^E \bmod 10^9\).

Because

$10^9=2^9\cdot 5^9,$

we distinguish two cases. If \(E<9\), then \(2^E\) can be computed directly. If \(E\ge 9\), then the residue modulo \(2^9\) is already fixed, and modulo \(5^9\) the powers of \(2\) repeat with multiplicative order

$\operatorname{ord}_{5^9}(2)=4\cdot 5^8=1{,}562{,}500.$

Therefore, for \(E\ge 9\),

$2^E \bmod 10^9 = 2^{\,9+((E-9)\bmod 1{,}562{,}500)} \bmod 10^9.$

So each grouped contribution only needs two pieces of data: the exponent modulo \(1{,}562{,}500\), and a capped indicator telling whether the true exponent is still below \(9\).

Step 5: Worked Example with \(HL(4)\)

We have

$L(4)=\operatorname{lcm}(1,2,3,4)=12=2^2\cdot 3.$

Hence the local choice counts are \(d=3\) for prime \(2\) and \(d=2\) for prime \(3\). There are four inclusion-exclusion cases:

$\begin{aligned} S=\varnothing &:&& M=3\cdot 2=6,\\ S=\{2\} &:&& M=2\cdot 2=4,\\ S=\{3\} &:&& M=3\cdot 1=3,\\ S=\{2,3\} &:&& M=2\cdot 1=2. \end{aligned}$

So

$HL(4)=H(12)=2^6-2^4-2^3+2^2=64-16-8+4=44.$

This is exactly the small checkpoint used by the implementation.

How the Code Works

The C++, Python, and Java implementations all follow the grouped inclusion-exclusion formula above. They first sieve the primes up to \(n\), then compute \(e_p\) and \(d_p=e_p+1\) for each prime using repeated integer division, which avoids any floating-point issues.

Next, they count how many times each \(d\)-value occurs and build one choice table per group. For every possible value \(i=0,\dots,c\) in a group of size \(c\), the table stores the signed binomial coefficient, the corresponding exponent factor modulo \(1{,}562{,}500\), and the capped information needed to detect whether the true exponent is still below \(9\).

After that, the implementation combines all groups except the largest into aggregate states. Each aggregate state represents many original subsets, but it keeps only the data required for the final modular evaluation. The last accumulation step pairs those aggregate states with the choices from the largest group and converts the stored exponent information into the correct value of \(2^E \bmod 10^9\).

The C++ implementation parallelizes that outer accumulation over several threads. The Python implementation performs the same arithmetic serially. The Java implementation acts as a thin wrapper around the same compiled computation, so all three language versions are numerically consistent.

Complexity Analysis

Let the distinct grouped values be \(d_1,\dots,d_t\) with multiplicities \(c_1,\dots,c_t\). A naive inclusion-exclusion over primes would require \(2^{\pi(n)}\) cases, which is hopeless for \(n=50000\). The grouped method reduces that to roughly

$\prod_{j=1}^{t}(c_j+1)$

combined choices, plus sieve and preprocessing work.

The prime sieve costs \(O(n\log\log n)\) time and \(O(n)\) memory. Building the per-group binomial data costs \(O\!\left(\sum_j c_j^2\right)\) time. The final state-combination phase is proportional to the grouped state count above, with extra practical speedup in the multithreaded C++ version. Memory usage is \(O(n)\) for the sieve plus the stored grouped states.

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=590
2. Least common multiple: Wikipedia - Least common multiple
3. Divisor function: Wikipedia - Divisor function
4. Inclusion-exclusion principle: Wikipedia - Inclusion-exclusion principle
5. Multiplicative order: Wikipedia - Multiplicative order