Problem 920: Tau Numbers

Project Euler Problem 920 Solution

EulerSolve provides an optimized solution for Project Euler Problem 920, Tau Numbers, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary A tau number is a positive integer $n$ for which the divisor count $\tau(n)$ divides $n$. With the fixed limit $L=10^{16}$, the problem asks us to look at every divisor-count value $k$ for which there exists at least one tau number $n\le L$ satisfying $\tau(n)=k$, and then define $$m(k)=\min\{n\le L:\tau(n)=k,\ k\mid n\}.$$ The required answer is the sum of all existing values $m(k)$. This includes the trivial case $m(1)=1$, but the real difficulty is global: for every reachable divisor count $k$, we must identify the smallest admissible integer rather than just produce one example. Mathematical Approach The implementations do not scan integers. They search over prime-exponent patterns, because both the divisor function and the condition $\tau(n)\mid n$ become rigid and testable in that language. Exponent vectors are the natural state space Write a candidate number as $$n=\prod_{i=1}^{r} b_i^{e_i},\qquad b_1<b_2<\cdots<b_r,\qquad e_1\ge e_2\ge \cdots\ge e_r\ge 1.$$ The exponents are arranged in non-increasing order because, once the multiset of exponents is fixed, the smallest possible integer is obtained by placing larger exponents on smaller primes. In this representation, the divisor count is $$\tau(n)=\prod_{i=1}^{r}(e_i+1)=:T.$$ So every exponent vector determines one divisor-count value $T$....

Detailed mathematical approach

Problem Summary

A tau number is a positive integer $n$ for which the divisor count $\tau(n)$ divides $n$. With the fixed limit $L=10^{16}$, the problem asks us to look at every divisor-count value $k$ for which there exists at least one tau number $n\le L$ satisfying $\tau(n)=k$, and then define

$$m(k)=\min\{n\le L:\tau(n)=k,\ k\mid n\}.$$

The required answer is the sum of all existing values $m(k)$. This includes the trivial case $m(1)=1$, but the real difficulty is global: for every reachable divisor count $k$, we must identify the smallest admissible integer rather than just produce one example.

Mathematical Approach

The implementations do not scan integers. They search over prime-exponent patterns, because both the divisor function and the condition $\tau(n)\mid n$ become rigid and testable in that language.

Exponent vectors are the natural state space

Write a candidate number as

$$n=\prod_{i=1}^{r} b_i^{e_i},\qquad b_1<b_2<\cdots<b_r,\qquad e_1\ge e_2\ge \cdots\ge e_r\ge 1.$$

The exponents are arranged in non-increasing order because, once the multiset of exponents is fixed, the smallest possible integer is obtained by placing larger exponents on smaller primes. In this representation, the divisor count is

$$\tau(n)=\prod_{i=1}^{r}(e_i+1)=:T.$$

So every exponent vector determines one divisor-count value $T$. Different vectors can yield the same $T$, which is why the search must keep the best number found for each divisor-count key.

The canonical lower bound that drives pruning

For the same exponent vector, the smallest possible realization is obtained by using the first $r$ primes:

$$n_{\min}(e_1,\dots,e_r)=\prod_{i=1}^{r} p_i^{e_i},$$

where $p_i$ is the $i$-th prime. This number does not necessarily satisfy $\tau(n)\mid n$; it is only the minimal number having that exponent multiset. But it is still crucial, because if even $n_{\min}(e_1,\dots,e_r)>L$, then every other realization of the same vector is larger, so the entire branch can be discarded immediately.

This lower bound is exactly what the outer depth-first search maintains incrementally. It is the main invariant that makes the global enumeration finite.

What $\tau(n)\mid n$ forces on the prime bases

Now factor the divisor count itself:

$$T=\prod_{j=1}^{t} q_j^{\nu_j},$$

with distinct primes $q_j$. Since $T\mid n$, every prime divisor $q_j$ of $T$ must also occur among the prime bases of $n$, and its exponent inside $n$ must be at least $\nu_j$.

For a fixed exponent vector, this turns into an injective placement problem. Each mandatory prime $q_j$ has to be assigned to a distinct exponent slot $i$ satisfying

$$e_i\ge \nu_j.$$

If there are more mandatory primes than slots, so $t>r$, the vector is impossible at once. Likewise, if the largest exponent is still smaller than one of the required values $\nu_j$, no assignment can work.

Minimizing one fixed exponent pattern

Suppose a feasible assignment $\sigma$ of the mandatory primes has been chosen. Then the resulting number has the form

$$N_\sigma=\left(\prod_{j=1}^{t} q_j^{e_{\sigma(j)}}\right)\left(\prod_{i\notin \operatorname{Im}(\sigma)} s_i^{e_i}\right),$$

where the remaining bases $s_i$ are distinct primes not dividing $T$. Once the mandatory primes are placed, the rest of the completion is forced greedily: fill the unused slots with the smallest available extra primes, matched from largest remaining exponent to smallest remaining exponent.

The justification is the swap inequality

$$a^x b^y\le a^y b^x\qquad(a<b,\ x\ge y),$$

which says that smaller primes belong on larger exponents. Therefore the only real branching for one vector is the placement of the mandatory primes. After that, the optimal completion is deterministic.

The best value attached to one exponent vector is therefore

$$M(e_1,\dots,e_r)=\min_{\sigma} N_\sigma,$$

and the desired minimum for a divisor-count value $k$ is

$$m(k)=\min_{\prod_{i=1}^{r}(e_i+1)=k} M(e_1,\dots,e_r).$$

Why the global search is complete

The outer DFS builds exponent vectors in non-increasing order. Starting from the smallest prime, each new exponent is constrained not to exceed the previous one, so every exponent multiset is visited exactly once in canonical form.

At each node, two quantities are already known:

$$\prod_{i=1}^{r} p_i^{e_i},\qquad T=\prod_{i=1}^{r}(e_i+1).$$

The first is the pruning bound just discussed; the second is the divisor-count value whose current minimum may be improved. Because many different exponent vectors can lead to the same $T$, the algorithm stores the best candidate found so far for each $T$. It also caches the prime factorization of $T$, since the same divisor count appears repeatedly during the search.

Worked Example: $k=12$

Take $k=12$. Since

$$12=2^2\cdot 3,$$

any tau number $n$ with $\tau(n)=12$ must contain the prime $2$ with exponent at least $2$, and it must also contain the prime $3$.

The exponent vectors satisfying

$$\prod(e_i+1)=12$$

are

$$[11],\qquad [5,1],\qquad [3,2],\qquad [2,1,1].$$

The vector $[11]$ is impossible because one slot cannot host both mandatory primes. For $[5,1]$, the smallest feasible number is

$$2^5\cdot 3=96.$$

For $[3,2]$, the best placement gives

$$2^3\cdot 3^2=72.$$

For $[2,1,1]$, the mandatory primes use the exponents $2$ and $1$, and the remaining slot receives the smallest extra prime not dividing $12$, namely $5$, producing

$$2^2\cdot 3\cdot 5=60.$$

Hence

$$m(12)=60.$$

This is exactly the comparison performed by the algorithm for every reachable divisor-count value.

How the Code Works

Outer enumeration and cached divisor factorizations

The C++, Python, and Java implementations first generate a sufficiently long prime table. Then they run an outer DFS over exponent vectors, maintaining the canonical product $\prod p_i^{e_i}$ and the current divisor count $T$ incrementally. Every visited node already represents a complete exponent pattern, so it is evaluated immediately as a candidate for its current $T$.

Whenever a node is visited, the implementation looks up or computes the prime factorization of $T$ and reuses that data through a cache. Capped multiplication is used throughout this stage so that any branch whose product would exceed $L$ stops immediately without overflow.

Inner assignment search, greedy completion, and symmetry pruning

For the current exponent vector, a second DFS assigns the mandatory primes from the factorization of $T$ to eligible slots. Those mandatory primes are tried in descending prime order so that expensive branches fail earlier, which strengthens pruning. If two unused slots have the same exponent, exploring both would only repeat a symmetric case, so the implementation keeps just one representative.

Once all mandatory primes have been placed, the unused slots are filled greedily with the smallest primes that do not divide $T$. The resulting number is compared against the best value already stored for that divisor-count key, and the map is updated only if an improvement has been found.

Complexity Analysis

There is no simple closed form for the total running time, because the outer search size depends on the number of non-increasing exponent vectors whose canonical realization satisfies

$$\prod_{i=1}^{r} p_i^{e_i}\le L.$$

If we denote that set by $V(L)$, then the outer DFS visits each vector in $V(L)$ exactly once.

For one vector with $r$ exponent slots and $t$ distinct prime factors in $T$, the inner search is a bounded backtracking procedure. Its naive worst case is exponential in $t$, but in practice the tree is cut down sharply by the slot-feasibility test, the limit $L$, the current best completion for the vector, the greedy tail fill, and the elimination of equal-exponent symmetries. Memory usage stays moderate: a prime table, a cache of divisor-count factorizations, recursion stacks, and the map of best values $m(k)$.

Footnotes and References

Project Euler problem page: https://projecteuler.net/problem=920
Divisor function: Wikipedia - Divisor function
Fundamental theorem of arithmetic: Wikipedia - Fundamental theorem of arithmetic
Backtracking: Wikipedia - Backtracking
Branch and bound: Wikipedia - Branch and bound

Problem 920 source code

C++

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <limits>
#include <unordered_map>
#include <unordered_set>
#include <vector>

namespace {

using u64 = std::uint64_t;
using u128 = unsigned __int128;

struct PrimeNeed {
    u64 prime;
    int need;
};

u64 pow_capped(u64 base, int exp, u64 cap) {
    u64 result = 1;
    for (int i = 0; i < exp; ++i) {
        if (result > cap / base) {
            return cap + 1;
        }
        result *= base;
    }
    return result;
}

u64 mul_pow_capped(u64 value, u64 base, int exp, u64 cap) {
    for (int i = 0; i < exp; ++i) {
        if (value > cap / base) {
            return cap + 1;
        }
        value *= base;
    }
    return value;
}

std::vector<int> sieve_primes(int max_n) {
    std::vector<bool> is_prime(max_n + 1, true);
    is_prime[0] = false;
    is_prime[1] = false;
    for (int i = 2; 1LL * i * i <= max_n; ++i) {
        if (!is_prime[i]) {
            continue;
        }
        for (int j = i * i; j <= max_n; j += i) {
            is_prime[j] = false;
        }
    }

    std::vector<int> primes;
    for (int i = 2; i <= max_n; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
        }
    }
    return primes;
}

std::string to_string_u128(u128 value) {
    if (value == 0) {
        return "0";
    }
    std::string out;
    while (value > 0) {
        out.push_back(static_cast<char>('0' + (value % 10)));
        value /= 10;
    }
    std::reverse(out.begin(), out.end());
    return out;
}

class TauSolver {
  public:
    explicit TauSolver(u64 limit) : limit_(limit), primes_(sieve_primes(300000)) {}

    std::unordered_map<u64, u64> compute_minimals() {
        best_.clear();
        factor_cache_.clear();
        std::vector<int> exponents;
        dfs_vectors(0, 64, 1, 1, exponents);
        return best_;
    }

  private:
    u64 limit_;
    std::vector<int> primes_;
    std::unordered_map<u64, std::vector<PrimeNeed>> factor_cache_;
    std::unordered_map<u64, u64> best_;

    const std::vector<PrimeNeed>& factorize(u64 x) {
        auto it = factor_cache_.find(x);
        if (it != factor_cache_.end()) {
            return it->second;
        }

        std::vector<PrimeNeed> factors;
        u64 value = x;
        for (int prime : primes_) {
            const u64 p = static_cast<u64>(prime);
            if (p * p > value) {
                break;
            }
            if (value % p != 0) {
                continue;
            }
            int exponent = 0;
            while (value % p == 0) {
                value /= p;
                ++exponent;
            }
            factors.push_back({p, exponent});
        }
        if (value > 1) {
            factors.push_back({value, 1});
        }

        auto [pos, _] = factor_cache_.emplace(x, std::move(factors));
        return pos->second;
    }

    std::vector<u64> build_extra_primes(int count, const std::vector<PrimeNeed>& mandatory) const {
        std::unordered_set<u64> blocked;
        blocked.reserve(mandatory.size() * 2 + 1);
        for (const PrimeNeed& req : mandatory) {
            blocked.insert(req.prime);
        }

        std::vector<u64> extras;
        extras.reserve(count);
        for (int prime : primes_) {
            const u64 p = static_cast<u64>(prime);
            if (blocked.find(p) != blocked.end()) {
                continue;
            }
            extras.push_back(p);
            if (static_cast<int>(extras.size()) == count) {
                break;
            }
        }
        return extras;
    }

    u64 minimal_value_for_vector(const std::vector<int>& exponents, const std::vector<PrimeNeed>& factors) {
        const int r = static_cast<int>(exponents.size());
        const int t = static_cast<int>(factors.size());
        if (t > r) {
            return limit_ + 1;
        }

        std::vector<PrimeNeed> mandatory = factors;
        std::sort(mandatory.begin(), mandatory.end(), [](const PrimeNeed& lhs, const PrimeNeed& rhs) {
            if (lhs.prime != rhs.prime) {
                return lhs.prime > rhs.prime;
            }
            return lhs.need > rhs.need;
        });

        for (const PrimeNeed& req : mandatory) {
            if (exponents.empty() || exponents.front() < req.need) {
                return limit_ + 1;
            }
        }

        const std::vector<u64> extras = build_extra_primes(r - t, mandatory);
        std::vector<bool> used(r, false);
        u64 best = limit_ + 1;

        const auto dfs_assign = [&](auto&& self, int idx, u64 current) -> void {
            if (current >= best) {
                return;
            }

            if (idx == t) {
                u64 value = current;
                int extra_idx = 0;
                for (int i = 0; i < r; ++i) {
                    if (used[i]) {
                        continue;
                    }
                    value = mul_pow_capped(value, extras[extra_idx], exponents[i], limit_);
                    if (value > limit_ || value >= best) {
                        return;
                    }
                    ++extra_idx;
                }
                best = std::min(best, value);
                return;
            }

            int previous_exp = -1;
            for (int i = 0; i < r; ++i) {
                if (used[i]) {
                    continue;
                }
                const int exp = exponents[i];
                if (exp < mandatory[idx].need) {
                    continue;
                }
                if (exp == previous_exp) {
                    continue;
                }
                previous_exp = exp;

                const u64 multiplied = mul_pow_capped(current, mandatory[idx].prime, exp, limit_);
                if (multiplied > limit_ || multiplied >= best) {
                    continue;
                }
                used[i] = true;
                self(self, idx + 1, multiplied);
                used[i] = false;
            }
        };

        dfs_assign(dfs_assign, 0, 1);
        return best;
    }

    void dfs_vectors(int prime_idx, int max_exp, u64 current_value, u64 tau_value, std::vector<int>& exponents) {
        const std::vector<PrimeNeed>& factors = factorize(tau_value);
        const u64 candidate = minimal_value_for_vector(exponents, factors);
        if (candidate <= limit_) {
            auto it = best_.find(tau_value);
            if (it == best_.end() || candidate < it->second) {
                best_[tau_value] = candidate;
            }
        }

        if (prime_idx >= static_cast<int>(primes_.size())) {
            return;
        }

        const u64 prime = static_cast<u64>(primes_[prime_idx]);
        u64 value = current_value;
        for (int exp = 1; exp <= max_exp; ++exp) {
            if (value > limit_ / prime) {
                break;
            }
            value *= prime;

            if (tau_value > std::numeric_limits<u64>::max() / static_cast<u64>(exp + 1)) {
                break;
            }
            const u64 new_tau = tau_value * static_cast<u64>(exp + 1);

            exponents.push_back(exp);
            dfs_vectors(prime_idx + 1, exp, value, new_tau, exponents);
            exponents.pop_back();
        }
    }
};

u128 sum_values(const std::unordered_map<u64, u64>& values) {
    u128 total = 0;
    for (const auto& [_, v] : values) {
        total += static_cast<u128>(v);
    }
    return total;
}

std::unordered_map<u64, u64> brute_minimals(int limit) {
    std::vector<int> tau(limit + 1, 0);
    for (int d = 1; d <= limit; ++d) {
        for (int multiple = d; multiple <= limit; multiple += d) {
            ++tau[multiple];
        }
    }

    std::unordered_map<u64, u64> best;
    for (int x = 1; x <= limit; ++x) {
        const int k = tau[x];
        if (x % k != 0) {
            continue;
        }
        const auto it = best.find(static_cast<u64>(k));
        if (it == best.end() || static_cast<u64>(x) < it->second) {
            best[static_cast<u64>(k)] = static_cast<u64>(x);
        }
    }
    return best;
}

void validate() {
    {
        TauSolver solver(1000);
        const auto minima = solver.compute_minimals();
        assert(minima.at(8) == 24);
        assert(minima.at(12) == 60);
        assert(minima.at(16) == 384);
        assert(sum_values(minima) == 3189);
    }

    {
        constexpr int kSmallLimit = 20000;
        TauSolver solver(kSmallLimit);
        const auto fast = solver.compute_minimals();
        const auto brute = brute_minimals(kSmallLimit);
        assert(fast.size() == brute.size());
        for (const auto& [k, value] : brute) {
            const auto it = fast.find(k);
            assert(it != fast.end());
            assert(it->second == value);
        }
    }
}

}  // namespace

int main() {
    validate();

    constexpr u64 kLimit = 10'000'000'000'000'000ULL;
    TauSolver solver(kLimit);
    const auto minima = solver.compute_minimals();
    std::cout << to_string_u128(sum_values(minima)) << '\n';
    return 0;
}

Python

def pow_capped(base, exp, cap):
    result = 1
    for _ in range(exp):
        if result > cap // base:
            return cap + 1
        result *= base
    return result

def mul_pow_capped(value, base, exp, cap):
    for _ in range(exp):
        if value > cap // base:
            return cap + 1
        value *= base
    return value

def sieve_primes(max_n):
    is_prime = [True] * (max_n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(max_n**0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, max_n + 1, i):
                is_prime[j] = False
    return [i for i, prime in enumerate(is_prime) if prime]

class TauSolver:
    def __init__(self, limit):
        self.limit = limit
        self.primes = sieve_primes(300000)
        self.factor_cache = {}
        self.best = {}

    def factorize(self, x):
        if x in self.factor_cache:
            return self.factor_cache[x]

        factors = []
        value = x
        for prime in self.primes:
            if prime * prime > value:
                break
            if value % prime == 0:
                exponent = 0
                while value % prime == 0:
                    value //= prime
                    exponent += 1
                factors.append({'prime': prime, 'need': exponent})
        if value > 1:
            factors.append({'prime': value, 'need': 1})

        self.factor_cache[x] = factors
        return factors

    def build_extra_primes(self, count, mandatory):
        blocked = {req['prime'] for req in mandatory}
        extras = []
        for prime in self.primes:
            if prime not in blocked:
                extras.append(prime)
                if len(extras) == count:
                    break
        return extras

    def minimal_value_for_vector(self, exponents, factors):
        r = len(exponents)
        t = len(factors)
        if t > r:
            return self.limit + 1

        mandatory = sorted(factors, key=lambda f: (-f['prime'], -f['need']))
        if mandatory and (not exponents or exponents[0] < mandatory[0]['need']):
            for req in mandatory:
                if not exponents or exponents[0] < req['need']:
                    return self.limit + 1

        extras = self.build_extra_primes(r - t, mandatory)
        used = [False] * r
        best = [self.limit + 1]

        def dfs_assign(idx, current):
            if current >= best[0]:
                return

            if idx == t:
                value = current
                extra_idx = 0
                for i in range(r):
                    if used[i]:
                        continue
                    value = mul_pow_capped(value, extras[extra_idx], exponents[i], self.limit)
                    if value > self.limit or value >= best[0]:
                        return
                    extra_idx += 1
                best[0] = min(best[0], value)
                return

            previous_exp = -1
            for i in range(r):
                if used[i]:
                    continue
                exp = exponents[i]
                if exp < mandatory[idx]['need']:
                    continue
                if exp == previous_exp:
                    continue
                previous_exp = exp

                multiplied = mul_pow_capped(current, mandatory[idx]['prime'], exp, self.limit)
                if multiplied > self.limit or multiplied >= best[0]:
                    continue
                used[i] = True
                dfs_assign(idx + 1, multiplied)
                used[i] = False

        dfs_assign(0, 1)
        return best[0]

    def dfs_vectors(self, prime_idx, max_exp, current_value, tau_value, exponents):
        factors = self.factorize(tau_value)
        candidate = self.minimal_value_for_vector(exponents, factors)
        if candidate <= self.limit:
            if tau_value not in self.best or candidate < self.best[tau_value]:
                self.best[tau_value] = candidate

        if prime_idx >= len(self.primes):
            return

        prime = self.primes[prime_idx]
        value = current_value
        for exp in range(1, max_exp + 1):
            if value > self.limit // prime:
                break
            value *= prime

            new_tau = tau_value * (exp + 1)

            exponents.append(exp)
            self.dfs_vectors(prime_idx + 1, exp, value, new_tau, exponents)
            exponents.pop()

    def compute_minimals(self):
        self.best.clear()
        self.factor_cache.clear()
        exponents = []
        self.dfs_vectors(0, 64, 1, 1, exponents)
        return self.best

def solve():
    kLimit = 10**16
    solver = TauSolver(kLimit)
    minima = solver.compute_minimals()
    ans = sum(minima.values())
    return str(ans)

if __name__ == "__main__":
    print(solve())

Java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Arrays;
import java.util.Collections;
import java.math.BigInteger;

public class Euler920 {

    static class PrimeNeed implements Comparable<PrimeNeed> {
        long prime;
        int need;

        PrimeNeed(long p, int n) {
            prime = p;
            need = n;
        }

        public int compareTo(PrimeNeed other) {
            if (this.prime != other.prime)
                return Long.compare(other.prime, this.prime);
            return Integer.compare(other.need, this.need);
        }
    }

    static long powCapped(long base, int exp, long cap) {
        long result = 1;
        for (int i = 0; i < exp; ++i) {
            if (result > cap / base)
                return cap + 1;
            result *= base;
        }
        return result;
    }

    static long mulPowCapped(long value, long base, int exp, long cap) {
        for (int i = 0; i < exp; ++i) {
            if (value > cap / base)
                return cap + 1;
            value *= base;
        }
        return value;
    }

    static List<Integer> sievePrimes(int maxN) {
        boolean[] isPrime = new boolean[maxN + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = false;
        isPrime[1] = false;
        for (int i = 2; (long) i * i <= maxN; ++i) {
            if (isPrime[i]) {
                for (int j = i * i; j <= maxN; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= maxN; ++i) {
            if (isPrime[i])
                primes.add(i);
        }
        return primes;
    }

    static class TauSolver {
        long limit;
        List<Integer> primes;
        Map<Long, List<PrimeNeed>> factorCache;
        Map<Long, Long> best;
        long bestValue;

        TauSolver(long limit) {
            this.limit = limit;
            this.primes = sievePrimes(300000);
            this.factorCache = new HashMap<>();
            this.best = new HashMap<>();
        }

        List<PrimeNeed> factorize(long x) {
            if (factorCache.containsKey(x))
                return factorCache.get(x);
            List<PrimeNeed> factors = new ArrayList<>();
            long value = x;
            for (int prime : primes) {
                if ((long) prime * prime > value)
                    break;
                if (value % prime == 0) {
                    int exponent = 0;
                    while (value % prime == 0) {
                        value /= prime;
                        exponent++;
                    }
                    factors.add(new PrimeNeed(prime, exponent));
                }
            }
            if (value > 1)
                factors.add(new PrimeNeed(value, 1));
            factorCache.put(x, factors);
            return factors;
        }

        List<Long> buildExtraPrimes(int count, List<PrimeNeed> mandatory) {
            java.util.Set<Long> blocked = new java.util.HashSet<>();
            for (PrimeNeed req : mandatory)
                blocked.add(req.prime);
            List<Long> extras = new ArrayList<>();
            for (int prime : primes) {
                long p = prime;
                if (!blocked.contains(p)) {
                    extras.add(p);
                    if (extras.size() == count)
                        break;
                }
            }
            return extras;
        }

        long minimalValueForVector(List<Integer> exponents, List<PrimeNeed> factors) {
            int r = exponents.size();
            int t = factors.size();
            if (t > r)
                return limit + 1;

            List<PrimeNeed> mandatory = new ArrayList<>(factors);
            Collections.sort(mandatory);

            for (PrimeNeed req : mandatory) {
                if (exponents.isEmpty() || exponents.get(0) < req.need)
                    return limit + 1;
            }

            List<Long> extras = buildExtraPrimes(r - t, mandatory);
            boolean[] used = new boolean[r];
            bestValue = limit + 1;

            dfsAssign(0, 1, r, t, mandatory, extras, exponents, used);
            return bestValue;
        }

        void dfsAssign(int idx, long current, int r, int t, List<PrimeNeed> mandatory, List<Long> extras,
                List<Integer> exponents, boolean[] used) {
            if (current >= bestValue)
                return;

            if (idx == t) {
                long value = current;
                int extraIdx = 0;
                for (int i = 0; i < r; ++i) {
                    if (used[i])
                        continue;
                    value = mulPowCapped(value, extras.get(extraIdx), exponents.get(i), limit);
                    if (value > limit || value >= bestValue)
                        return;
                    extraIdx++;
                }
                bestValue = Math.min(bestValue, value);
                return;
            }

            int previousExp = -1;
            for (int i = 0; i < r; ++i) {
                if (used[i])
                    continue;
                int exp = exponents.get(i);
                if (exp < mandatory.get(idx).need)
                    continue;
                if (exp == previousExp)
                    continue;
                previousExp = exp;

                long multiplied = mulPowCapped(current, mandatory.get(idx).prime, exp, limit);
                if (multiplied > limit || multiplied >= bestValue)
                    continue;

                used[i] = true;
                dfsAssign(idx + 1, multiplied, r, t, mandatory, extras, exponents, used);
                used[i] = false;
            }
        }

        void dfsVectors(int primeIdx, int maxExp, long currentValue, long tauValue, List<Integer> exponents) {
            List<PrimeNeed> factors = factorize(tauValue);
            long candidate = minimalValueForVector(exponents, factors);
            if (candidate <= limit) {
                if (!best.containsKey(tauValue) || candidate < best.get(tauValue)) {
                    best.put(tauValue, candidate);
                }
            }

            if (primeIdx >= primes.size())
                return;

            long prime = primes.get(primeIdx);
            long value = currentValue;
            for (int exp = 1; exp <= maxExp; ++exp) {
                if (value > limit / prime)
                    break;
                value *= prime;

                long newTau = tauValue * (exp + 1);

                exponents.add(exp);
                dfsVectors(primeIdx + 1, exp, value, newTau, exponents);
                exponents.remove(exponents.size() - 1);
            }
        }

        Map<Long, Long> computeMinimals() {
            best.clear();
            factorCache.clear();
            List<Integer> exponents = new ArrayList<>();
            dfsVectors(0, 64, 1, 1, exponents);
            return best;
        }
    }

    public static String solve() {
        long kLimit = 10000000000000000L;
        TauSolver solver = new TauSolver(kLimit);
        Map<Long, Long> minima = solver.computeMinimals();
        BigInteger total = BigInteger.ZERO;
        for (long v : minima.values()) {
            total = total.add(BigInteger.valueOf(v));
        }
        return total.toString();
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}