Project Euler Problem 920
For a positive integer n we define tau(n) to be the count of the divisors of n.
Solution
Answer: 1154027691000533893
Let
$$n=\prod p_i^{a_i}$$
Then
$$\tau(n)=\prod (a_i+1).$$
For a fixed divisor count $k$, every factorization
$$k=\prod (a_i+1)$$
corresponds to a possible exponent pattern $(a_i)$.
To obtain the smallest tau number $m(k)$, we must additionally require
$$k \mid n.$$
That means every prime factor of $k$ must appear in $n$ with sufficient exponent.
A complete search over all exponent patterns whose minimal realization is $\le 10^{16}$ is feasible.
The algorithm:
- Generate all admissible exponent vectors $(a_1\ge a_2\ge \cdots)$ whose ordinary minimal number is $\le 10^{16}$.
- For each corresponding divisor count $k=\prod(a_i+1)$:
- assign exponents to primes so that $k\mid n$,
- minimize the resulting value of $n$,
- record the smallest valid $m(k)$.
- Sum all $m(k)\le 10^{16}$.
The implementation reproduces the check value:
$$M(3)=3189.$$
Running the full computation for $10^{16}$ gives:
$$M(16)=1154027691000533893.$$
Answer: 1154027691000533893