Let $\sigma_k(n)$ denote the sum of the k-th powers of the divisors of n. For any real value of k, we can find a sequence of numbers $s_k$ that has increasing values of n at which $\sigma_k(n)$ attains a new maximum. For k=0, that sequence is called the highly composite numbers, which is A002182 in the OEIS database. From numerical experimentation, it appears that if i > j >= 0, then $s_j$ is a subsequence of $s_i$. Is this a known result? If not, any ideas on how to prove it?
3
-
$\begingroup$ It was just pointed out to me that 1084045767585249647898720000 provides a counterexample: it is in $s_0$ but not in $s_1$. $\endgroup$– tdnoeCommented Oct 11, 2010 at 17:32
-
$\begingroup$ Start with L. Alaoglu and P. Erdos, On highly composite and similar numbers, Trans. Amer. Math. Soc., 56 (1944), 448-469. $$ $$ en.wikipedia.org/wiki/Highly_abundant_number $$ $$ oeis.org/classic/A002093 $\endgroup$– Will JagyCommented Oct 11, 2010 at 17:39
-
$\begingroup$ There are ten counterexamples in the new sequence oeis.org/classic/A181309 $\endgroup$– tdnoeCommented Oct 19, 2010 at 15:56
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
It appears you got an answer while I was typing my comment. But let me expand the picture a bit. Ramanujan initiated a technique for finding certain subsequences of yours that possess a parametrization, where the highly composite numbers do not. First, see two articles,
http://en.wikipedia.org/wiki/Superior_highly_composite_number
http://en.wikipedia.org/wiki/Colossally_abundant_number
The recipe is very simple, with one detail that is not usually pointed out: to define the sequence of "superior" numbers, note that for any $\varepsilon > 0,$ we can prove $$ \lim_{n \rightarrow \infty} \frac{\sigma_k(n)}{n^{k + \varepsilon}} = 0. $$ As a result, for any fixed $\varepsilon > 0,$ the ratio attains a maximum at a finite number of integers (usually just one). If the maximum is attained at more than one integer, take the largest of these, and call that $S_\varepsilon.$ As $\varepsilon$ decreases $S_\varepsilon$ stays the same until $\varepsilon$ passes below the next of a sequence of threshold values, and then at the threshold is multiplied by a certain prime. So we get an increasing sequence $S_\varepsilon,$ each a multiple of all before it, and each setting a new record for $\sigma_k.$
Now, about the recipe, the construction, if you work through it carefully, gives a specific prime factorization for $S_\varepsilon,$ where the exponent for any prime depends on $\varepsilon$ in a way that involves the greatest integer function $\lfloor \bullet \rfloor. $ However, as $\varepsilon$ decreases, the relative sizes of the exponents for two primes, say 2 and 3, depend upon the value of $k.$ And these sequences are a subsequence of yours. So, despite that fact that there are so many more numbers of a given size in one of your sequences, what this says to me is that we should not expect too much agreement for differing $k.$ At the same time, there are papers on the difficult Operations Research aspects of finding large highly composite numbers, say all those between two consecutive "superior" numbers. Thus the first disagreement (showing one is not a subsequence of the other) of two of your sequences may occur at a huge number, as you found.
Well, for $k=1$ this was written up by Alaoglu and Erdos. It was later discovered that Ramanujan did write this up as well, but the journal declined to publish the full length article owing to shortages of paper in 1915.
Contemporary authors working in this area include J.-L. Nicolas and G. Robin. Perhaps the most dramatic use of these numbers is that the Riemann hypothesis is equivalent to the statement that for $n > 5040,$ $$ \sigma_1(n) < e^\gamma n \log \log n, $$ and that any possible counterexample must occur at a colossally abundant number
answered Oct 11, 2010 at 18:18