Detailed mathematical approach

Problem Summary

We study factor pairs of \(100!\). For every pair \((a,b)\) with \(ab=100!\) and \(a\le b\), we ask whether \(a\) and \(b\) have the same number of positive divisors. If \(\tau\) denotes the divisor-counting function, the required quantity is

$C(100!)=\#\left\{(a,b):ab=100!,\ a\le b,\ \tau(a)=\tau(b)\right\}.$

A naive scan over all divisors of \(100!\) is far too large. The successful approach works with prime exponents and balances the prime factors of \(\tau(a)\) and \(\tau(b)\) instead of comparing \(a\) and \(b\) directly.

Mathematical Approach

Write the prime factorization of \(100!\) as

$100!=\prod_{p\le 100} p^{e_p},\qquad e_p=\sum_{k\ge 1}\left\lfloor\frac{100}{p^k}\right\rfloor.$

Each prime \(p\) contributes an exponent \(e_p\), and every factor pair of \(100!\) comes from deciding how much of that exponent belongs to \(a\) and how much belongs to \(b\).

Step 1: Encode Every Factor Pair by Exponent Choices

Choose integers \(x_p\) with \(0\le x_p\le e_p\) and define

$a=\prod_{p\le 100} p^{x_p},\qquad b=\prod_{p\le 100} p^{e_p-x_p}.$

Every ordered factorization \(ab=100!\) arises exactly once in this way. The divisor-count formulas become

$\tau(a)=\prod_{p\le 100}(x_p+1),\qquad \tau(b)=\prod_{p\le 100}(e_p-x_p+1).$

So the problem reduces to choosing one integer from each interval \(0,\dots,e_p\) so that these two products are equal.

Step 2: Turn \(\tau(a)=\tau(b)\) into Prime-Valuation Balances

Two positive integers are equal if and only if every prime appears with the same exponent in both. Therefore \(\tau(a)=\tau(b)\) is equivalent to

$\sum_{p\le 100}\nu_q(x_p+1)=\sum_{p\le 100}\nu_q(e_p-x_p+1).$

This identity must hold for every prime \(q\).

Define the balance at prime \(q\) by

$D_q=\sum_{p\le 100}\left(\nu_q(x_p+1)-\nu_q(e_p-x_p+1)\right).$

Then a choice of exponents is valid exactly when

$D_q=0.$

This must again hold for every prime \(q\).

This reformulation is the core of the method: we count exponent assignments whose valuation-balance vector is identically zero.

Step 3: Why \(2,3,5,7\) Are the Exceptional Primes

Legendre's formula gives

$e_2=97,\qquad e_3=48,\qquad e_5=24,\qquad e_7=16,$

while every prime \(p>7\) satisfies

$e_p\le 9.$

Hence, for \(p>7\), the numbers \(x_p+1\) and \(e_p-x_p+1\) always lie between \(1\) and \(10\). Their prime factors can only belong to

$\{2,3,5,7\}.$

That means every prime \(p>7\) can affect only the four balances \(D_2,D_3,D_5,D_7\). It can never create or cancel a balance at any larger prime \(q>7\).

Step 4: Split the Search into Two Independent Parts

The previous observation implies that every balance \(D_q\) with \(q>7\) must already vanish inside the contribution coming from \(p\in\{2,3,5,7\}\). The search therefore splits naturally.

First, enumerate all choices for the four exceptional primes \(2,3,5,7\). For each choice, compute the full balance vector \((D_q)\). Since \(x_2+1\) can be as large as \(98\), this stage may involve primes such as \(11,13,\dots,97\). Keep only those assignments for which every coordinate with \(q>7\) is already zero.

After that filter, only the four coordinates

$\left(D_2,D_3,D_5,D_7\right)$

still matter. Second, process the primes \(p>7\). Each such prime contributes one small four-dimensional delta vector, because only \(2,3,5,7\) can appear in the corresponding divisor-count factors.

Step 5: Match Complementary Four-Dimensional States

Let \(\mathbf d=(d_2,d_3,d_5,d_7)\) be a state produced by the exceptional primes after the large-prime balances have been forced to zero. Let \(\mathbf r\) be a state produced by the remaining primes. A complete exponent assignment is valid exactly when

$\mathbf d+\mathbf r=\mathbf 0.$

So the ordered answer is obtained by counting, for every state from the exceptional-prime side, how many states from the remaining-prime side are its exact negative.

Step 6: Convert Ordered Solutions to the Requested Unordered Pairs

The construction above counts ordered pairs \((a,b)\). The problem asks for unordered pairs with \(a\le b\). Swapping \(a\) and \(b\) replaces every \(x_p\) by \(e_p-x_p\), so non-fixed solutions come in symmetric pairs. Therefore

$C(100!)=\frac{M+F}{2},$

where \(M\) is the ordered count and \(F=1\) only if \(100!\) is a perfect square. Here \(F=0\), because not all exponents \(e_p\) are even.

Worked Example: \(10!\)

The same machinery is easy to inspect on

$10!=2^8\cdot 3^4\cdot 5^2\cdot 7.$

In this smaller case there are no primes \(p>7\), so only the exceptional stage remains. The primes \(5\) and \(7\) together can produce the six balances

$(-1,-1,0,0),\ (-1,0,0,0),\ (-1,1,0,0),\ (1,-1,0,0),\ (1,0,0,0),\ (1,1,0,0).$

The primes \(2\) and \(3\) produce the opposite balances with multiplicities \(2,1,1,2\) on the four vectors

$(-1,0,0,0),\ (-1,1,0,0),\ (1,-1,0,0),\ (1,0,0,0),$

and no matches for \((-1,-1,0,0)\) or \((1,1,0,0)\). Hence the ordered count is

$M=2+1+1+2=6.$

Since \(10!\) is not a square, \(F=0\), so

$C(10!)=\frac{6}{2}=3.$

This is the small checkpoint reproduced by the implementation.

How the Code Works

The C++, Python, and Java implementations follow the same pipeline. They first generate all primes up to \(100\) and compute every exponent \(e_p\) with Legendre's formula. Next they precompute the prime factorizations of all integers from \(1\) to \(\max(e_p)+1\). That turns every quantity of the form \(\nu_q(x_p+1)\) or \(\nu_q(e_p-x_p+1)\) into a fast table lookup.

For the exceptional primes \(2,3,5,7\), the implementation enumerates every possible complementary pair \((x_p+1,e_p-x_p+1)\), builds the corresponding balance vectors, and merges them in two batches before forming the full four-prime combinations. Only combinations whose coordinates for primes \(q>7\) are all zero are kept, and their remaining four-coordinate balances are stored with multiplicities.

For each prime \(p>7\), the implementation computes all possible deltas on \((D_2,D_3,D_5,D_7)\) and updates a sparse map from four-dimensional balance states to counts. The ordered total is the sum of products of matching complementary states from the two stages. A final symmetry correction converts that ordered total into the requested count with \(a\le b\).

Complexity Analysis

Let

$A=(e_2+1)(e_3+1)(e_5+1)(e_7+1).$

Enumerating the exceptional primes costs \(O(A\cdot B)\), where \(B\) is the number of prime coordinates that may appear in the divisor-count factors. For \(100!\), this is practical because only four primes have large exponent ranges.

For the remaining primes, if \(S_k\) denotes the number of distinct four-dimensional states after processing the first \(k\) primes greater than \(7\), then the dynamic program costs

$O\left(\sum_k S_{k-1}(e_{p_k}+1)\right)$

time and \(O(\max_k S_k)\) memory. Since every prime \(p>7\) has \(e_p+1\le 10\), the branching factor is tiny and the sparse state space stays manageable.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=598
2. Divisor function: Wikipedia - Divisor function
3. Legendre's formula: Wikipedia - Legendre's formula
4. Prime factorization: Wikipedia - Prime factorization
5. \(p\)-adic valuation: Wikipedia - \(p\)-adic valuation