2
$\begingroup$

This is the sequence of prime numbers which are the elementary building blocks for the superior highly composite numbers:

$2, 3, 2, 5, 2, 3, 7, 2, 11, 13, 2, 3, 5, 17, 19, 2, 23, ...$

The $n^{th}$ superior highly composite number is the product of the first $n$ primes in this sequence.

What I would like to know is where do these primes come from?
Is there a formula which directly gives what is the $n^{th}$ term in this sequence? Or some other kind of relation?

At first I thought that the $n^{th}$ term in this sequence was the smallest prime $p$ such that $p^{a+1}$ is the smallest as possible, where $a$ is the number of times $p$ has already occurred in the sequence.
This correctly predicts the first $4$ terms: $2, 3, 2, 5$
But then it predicts that the next few terms are $7, 2, 3$ instead of $2, 3, 7$
So that's clearly not the answer.

$\endgroup$
5
  • 2
    $\begingroup$ For those that do not know what a superior highly composite number is: en.wikipedia.org/wiki/Superior_highly_composite_number $\endgroup$ Oct 27, 2014 at 11:45
  • 4
    $\begingroup$ And the sequence in question: oeis.org/A000705 $\endgroup$ Oct 27, 2014 at 11:45
  • $\begingroup$ start off with this answer mathoverflow.net/questions/43103/… $\endgroup$
    – Will Jagy
    Oct 27, 2014 at 18:04
  • $\begingroup$ What does: a natural number which has more divisors than any other number scaled relative to the number itself mean? Whatever this would mean, it sounds that there is at most one. $\endgroup$ Oct 27, 2014 at 19:45
  • $\begingroup$ @WłodzimierzHolsztyński, grammar notwithstanding, it means the number that gives the maximum value of $d(n)/ n^\delta$ for a fixed real $\delta > 0.$ Proof that there is a maximum is in Hardy and Wright, for example. $\endgroup$
    – Will Jagy
    Oct 27, 2014 at 20:10

1 Answer 1

6
$\begingroup$

No, no formula. The correct way to get the SHC numbers in order is to use Ramanujan's original recipe. For any prime $p$ and any integer exponent $k \geq 1$ calculate the real number $$ \delta = \frac{\log \left(1 + \frac{1}{k} \right)}{\log p}. $$ As this is smaller than $1/ (k \log p)$ there are only finitely many pairs $(p,k)$ such that $\delta$ is above a given lower bound. Print those out, then print them out with the $\delta$ column in decreasing order. The ordered list tells you which prime comes next. I used lower bound $0.145.$ First, raw output:

1.0000000000000000           2           1
0.5849625007211562           2           2
0.4150374992788437           2           3
0.3219280948873623           2           4
0.2630344058337938           2           5
0.2223924213364480           2           6
0.1926450779423958           2           7
0.1699250014423124           2           8
0.1520030934450501           2           9
0.6309297535714574           3           1
0.3690702464285426           3           2
0.2618595071429148           3           3
0.2031140135750123           3           4
0.1659562328535302           3           5
0.4306765580733931           5           1
0.2519296364125923           5           2
0.1787469216608008           5           3
0.3562071871080222           7           1
0.2083678469455574           7           2
0.1478393401624647           7           3
0.2890648263178878          11           1
0.1690920836734384          11           2
0.2702381544273197          13           1
0.1580791866040749          13           2
0.2446505421182260          17           1
0.2354089133666382          19           1
0.2210647294575037          23           1
0.2058468324604344          29           1
0.2018490865820999          31           1
0.1919587200065601          37           1
0.1866524112389434          41           1
0.1842888331487062          43           1
0.1800313266566926          47           1
0.1745834300480449          53           1
0.1699916162869140          59           1
0.1686130986895011          61           1
0.1648508567221603          67           1
0.1626083122716342          71           1
0.1615554674429964          73           1
0.1586349589155960          79           1
0.1568617748594410          83           1
0.1544226628011101          89           1
0.1515171524096389          97           1

Next, ordered by decreasing $\delta.$ You can read off the next prime in the second column, and the exponent of that prime in the resulting SHC number in the final column:

1.0000000000000000           2           1
0.6309297535714574           3           1
0.5849625007211562           2           2
0.4306765580733931           5           1
0.4150374992788437           2           3
0.3690702464285426           3           2
0.3562071871080222           7           1
0.3219280948873623           2           4
0.2890648263178878          11           1
0.2702381544273197          13           1
0.2630344058337938           2           5
0.2618595071429148           3           3
0.2519296364125923           5           2
0.2446505421182260          17           1
0.2354089133666382          19           1
0.2223924213364480           2           6
0.2210647294575037          23           1
0.2083678469455574           7           2
0.2058468324604344          29           1
0.2031140135750123           3           4
0.2018490865820999          31           1
0.1926450779423958           2           7
0.1919587200065601          37           1
0.1866524112389434          41           1
0.1842888331487062          43           1
0.1800313266566926          47           1
0.1787469216608008           5           3
0.1745834300480449          53           1
0.1699916162869140          59           1
0.1699250014423124           2           8
0.1690920836734384          11           2
0.1686130986895011          61           1
0.1659562328535302           3           5
0.1648508567221603          67           1
0.1626083122716342          71           1
0.1615554674429964          73           1
0.1586349589155960          79           1
0.1580791866040749          13           2
0.1568617748594410          83           1
0.1544226628011101          89           1
0.1520030934450501           2           9
0.1515171524096389          97           1
0.1478393401624647           7           3

It is a theorem of Siegel that there cannot be three different primes $p,q,r$ and three different positive integer exponents $i,j,k$ such that $(p,k); (q,i); (r,j)$ all give the same $\delta$ value. This still leaves the distressing possibility of two primes matching, although no-one expects this, and of course it has never been seen regardless of how far computations have been done.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.