I'm seeking an efficient implementation of the number-theoretic function giving the smallest integer $n$ that has exactly $k$ factors (not necessarily prime):
f[k_Integer]:= ...
f[1] = 1
because $1$ is the smallest integer that has just a single factor, i.e., $\{ 1 \}$f[2] = 2
because $2$ is the smallest integer that has just the two factors, i.e., $\{ 1, 2 \}$f[3] = 4
because $4$ is the smallest integer that has exactly three factors, i.e., $\{ 1, 2, 4 \}$f[4] = 6
because $6$ is the smallest integer that has exactly four factors, i.e., $\{ 1, 2, 3, 6 \}$f[5] = 16
because $16$ is the smallest integer that has exactly five factors, i.e., $\{ 1, 2, 4, 8, 16 \}$f[6] = 12
because $12$ is the smallest integer that has exactly six factors, i.e., $\{ 1, 2, 3, 4, 6, 12 \}$f[7] = 64
because $64$ is the smallest integer that has exactly seven factors, i.e., $\{ 1, 2, 4, 8, 16, 32, 64 \}$f[8] = 24
because $24$ is the smallest integer that has exactly eight factors, i.e., $\{ 1, 2, 3, 4, 6, 8, 12, 24 \}$f[9] = 36
because $36$ is the smallest integer that has exactly nine factors, i.e., $\{ 1, 2, 3, 4, 6, 9, 12, 18, 36 \}$
A few moments of thought will show that for $k$ odd, $n$ is a perfect square. Moreover, note that f[k]
is not monotonic.
Very inefficient code would advance through increasing $n$ until an integer is found with the criterion of exactly $k$ factors, but this is extremely inefficient for large $k$.
This generates the pairs $n,k$ up to $n=100$:
myList = Table[{n, Times @@ (# + 1 & /@ FactorInteger[n][[All, 2]])},
{n, 2, 100}]
And it is a simple matter to select cases with a given $k$:
Select[myList, #[[2]] == 60]
When $k \sim 10^6$, this is somewhat slow and definitely memory intensive.
As background/edification, here is a log plot of $n$ versus $k$.
In 1644, the great mathematician Mersenne asked for f[60] = 5040
.
f[60] = 5040
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 28, 30, 35, 36, 40, 42, 45, 48, 56, 60, 63, 70, 72, 80, 84, 90, 105, 112, 120, 126, 140, 144, 168, 180, 210, 240, 252, 280, 315, 336, 360, 420, 504, 560, 630, 720, 840, 1008, 1260, 1680, 2520, 5040}
is surprisingly fast. $\endgroup$ – bbgodfrey Nov 21 '18 at 3:12f[10^6]
and even higher, without having to calculate billions of "lower" cases. $\endgroup$ – David G. Stork Nov 21 '18 at 3:15Table[f[k], {k, 1, 20, 1}]
is{1, 2, 4, 6, 16, 12, 64, 24, 36, 48, 1024, 60, 4096, 192, 144, 120, 65536, 180, 262144, 240}
. Check yourf[4]
. $\endgroup$ – bbgodfrey Nov 21 '18 at 3:20