[Math] Smallest number with a given number of factors

divisibilityfactoringnumber theory

From my rather rudimentary explorations of this fascinating problem, I believe it to be a layered and rewarding subject for investigation.

My question, essentially, is: How do you find the smallest number with a given number of factors? Indeed, as quickly becomes apparent, a distinction is called for between exactly a given number of factors and at least a given number of factors; as such, approaches considering both will be appreciated.

It's a fairly standard result in number theory that the number of distinct factors (including $1$ and itself) of some number $N$, where
$$
N = p_1^{a}\cdot\ p_2^{b}\cdot\ p_3^{c} \cdots
$$
($p_1$, $p_2$, $p_3\ldots$ being distinct primes) is
$$
(a+1)(b+1)(c+1)\cdots
$$

Thus, stated mathematically, the question appears to resolve into finding, or rather, finding a method of finding, this:
$$
\min\{N = 2^{a}\cdot\ 3^{b}\cdot\ 5^{c} \cdots \space| \space (a+1)(b+1)(c+1)\cdots = n \}
$$
or, as the case may be, this:
$$
\min\{N = 2^{a}\cdot\ 3^{b}\cdot\ 5^{c} \cdots \space| \space (a+1)(b+1)(c+1)\cdots \geq n \}
$$
($n$ being the given number of factors).

My crude, trial-and-error approach so far has been factorising $n$ into $n = n_1\cdot n_2\cdot n_3\cdots \space$ and then assigning $a = n_1 – 1,\space b = n_2 – 1,\space c = n_3 – 1,\space \ldots \space$ to get $N$, my only defence being that I tried to factorise sensibly and perceive some sort of pattern or rule at play. I have been unable to obtain anything beyond some common-sense tricks and techniques, though some of them seemed tantalisingly concrete.

I think it's a beautiful problem, and I'm looking for a way of solving it using a clever, universal algorithm. I'd greatly appreciate a comprehensive solution.

Best Answer

For the at least case, you should check out OEIS sequence A002182 which lists the numbers which set records for number of factors. Many references are given. For exactly equal, see A005179 which has the smallest number with a given number of divisors.

Related Solutions

[Math] Number of factorizations of distinct factors

Special cases

For $n = p_i p_2 \cdots p_k$, (all with exponent $1$), the multiplicative partitions $m_1, m_2,\dots, m_{k+1}$ are given by the coefficients of the expanded series $$f(x,k)=\dfrac{1-(k-1) x}{\prod _{n=1}^k (1-n x)}$$ where the $m$th partition of $p_1 p_2 \cdots p_k$ is give by the $(k-m+2)$th coefficient.

f[k_] := (1 - (k - 1) x)/Product[1 - n x, {n, 1, k}]
g[a_, b_] := CoefficientList[Series[f@b, {x, 0, b + a}], x][[a - b + 2]]
h[n_] := g[n, #] & /@ Range[n + 1]

h[#] & /@ Range@6

gives

\begin{array}{c} 1 & 1\\ 1 & 2 & 1\\ 1 & 4 & 4 & 1\\ 1 & 8 & 13 & 7 & 1\\ 1 & 16 & 40 & 35 & 11 & 1\\ 1 & 32 & 121 & 155 & 80 & 16 & 1\\ \end{array}

eg $30$ has partitions of length $m_1=1,\ m_2=4,\ m_3=4,\ m_4=1$:

$m_1=1$:

$30$

$m_2=4$:

$1 \times 30$
$2 \times 15$
$3 \times 10$
$5 \times 6$

$m_3=4$:

$1 \times 2 \times 15$
$1 \times 3 \times 10$
$1 \times 5 \times 6$
$2 \times 3 \times 5$

$m_4=1$:

$1 \times 2 \times 3 \times 5$

The multiplicative partitions $m_1,m_2,\dots,m_{\left\lfloor \sqrt{2 (k+1)}+1/2\right\rfloor}$ for $p^k$ (where $p$ is prime) are given by the coefficients of the expanded series $$f_1(x,k)=\dfrac{1}{\prod _{n=1}^k (1-x^n)}$$ where the $m$th partition is give by the $(m+ 1 - k(k- 1)/2)$th coefficient.

f1[k_] := 1/Product[(1 - x^n), {n, 1, k}]
g1[a_, b_] := CoefficientList[Series[f1@b, {x, 0, b + a}], x][[1 - b (b - 1)/2 + a]]
h1[n_] := g1[n, #] & /@ Range@Floor[Sqrt[2 (n + 1)] + 1/2]

h1[#] & /@ Range@6

gives

\begin{array}{c} 1 & 1\\ 1 & 1\\ 1 & 2 & 1\\ 1 & 2 & 1\\ 1 & 3 & 2\\ 1 & 3 & 3 & 1\\ \end{array}

eg $512$ has partitions of length $m_1=1,\ m_2=5,\ m_3=7,\ m_4=3$.

$m_1=1$:

$512$

$m_2=5$:

$1 \times 512$
$2 \times 256$
$4 \times 128$
$8 \times 64$
$16 \times 32$

$m_3=7$:

$1 \times 2 \times 256$
$1 \times 4 \times 128$
$1 \times 8 \times 64$
$1 \times 16 \times 32$
$2 \times 4 \times 64$
$2 \times 8 \times 32$
$4 \times 8 \times 16$

$m_4=3$:

$1 \times 2 \times 4 \times 64$
$1 \times 2 \times 8 \times 32$
$1 \times 4 \times 8 \times 16$

It would be nice to find a generalised solution for any $p_i^{e_1} p_2^{e_2} \cdots p_k^{e_k}$, but not sure whether this is easiliy attainable.

The best algorithm for finding Goldbug Numbers

I am posting the code from the forum written by UAU. This is the best implementation to date and identifies 6 Goldbug numbers under 100k. Keep in mind for speed this is searching for the maximal set and there can be subsets of the maximal set which satisfy the Goldbug property. I have run the code and verified it produces 6 Goldbugs under 100k (128,1718,1862,1928,2200,6142). For more details see the original post:

https://www.mersenneforum.org/showpost.php?p=501714&postcount=23

Thanks UAU!

#!/usr/bin/python3
import sys

def sieve(n):
    n //= 2
    r = [[] for _ in range(n)]
    for x in range(1, n):
        if r[x]:
            continue
        r[x] = None
        y = 3*x+1
        while y < n:
            r[y].append(2*x+1)
            y += x+x+1
    return r

def check(n, r):
    s = {}
    for i in range(3, n//2, 2):
        if r[i>>1] is not None or not n % i:
            continue
        for f in r[(n-i)>>1] or [n-i]:
            s.setdefault(f, []).append(i)
    bad = [x for x in s if x >= n//2]
    bad_seen = set(bad)
    ok = set(i for i in range(3, n // 2, 2) if r[i>>1] is None and n % i)
    while bad:
        x = s.get(bad.pop(), ())
        for p in x:
            if p not in bad_seen:
                bad.append(p)
                bad_seen.add(p)
                ok.discard(p)
    return ok

def search(lim):
    r = sieve(lim)
    for i in range(2, lim, 2):
        x = check(i, r)
        if x:
             print(i, sorted(x))

search(int(sys.argv[1]))

Best Answer

Related Solutions

[Math] Number of factorizations of distinct factors

The best algorithm for finding Goldbug Numbers

Related Question