Colossally abundant numbers are positive integers $n$ for which there exists a positive exponent $\epsilon$ such that
$$\frac{\sigma(n)}{n^{1+\epsilon}}>\frac{\sigma(m)}{m^{1+\epsilon}}$$
for all integers $m>1,m\ne n$. Here, $\sigma(n)$ denotes the sum-of-divisors function $\sum_{d|n}d$.
The first few colossally abundant numbers are $2,6,12,60,120,360...$ (from Wolfram Mathworld here).
My question is, how does one go about discovering such numbers, or proving that a number is colossally abundant? One can't test individually for all combinations of $n,m,\epsilon$, so there must be an algebraic method. What is it? (Google is no help.)
UPDATE
In light of @Mindlack's and @John Omielan's helpful comments below, and in order not to end up with an extended comment section, I thought it might be good to elaborate on my original question here.
- @John: Yes, I take your point, but it still sounds a lot like searching for a needle in a haystack. Maybe that's what you're trying to say?
- @Mindlack:
- OK, so setting $n=2$ gives $\frac{\sigma(n)}{n^{1+\epsilon}}=\frac{\sigma(2)}{2^{1+\epsilon}}=\frac{3}{2^{1+\epsilon}}$, with you so far
- But where does $\frac{\sigma(n)}{n}=\sum_{d|n}\frac{n/d}{n}$ come from? It seems to me that we have $\frac{\sigma(n)}{n}=\frac{\sum_{d|n}d}{n}$. So you are suggesting that $\frac{\sum_{d|n}d}{n}=\sum_{d|n}\frac{n/d}{n}$... How so? Surely we should have $\frac{\sigma(n)}{n}=\frac{\sum_{d|n}d}{n}=\sum_{d|n}\frac{d}{n}$
- And... well, there I lose you. I can't follow the rest because I can't really get past this one issue
I'm 100% sure it's me being stupid - I'm teaching myself all this stuff for the first time, and on my own. I realise that no one on MathStackExchange signs up to hold the hands of newbies, but if you have the time (or anyone else does) I'd really appreciate some clarification.
BTW: aren't we all, as a community and as a species, incredibly that such sites exist? Wow.
$\endgroup$ 85 Answers
$\begingroup$Given some $\delta > 0,$ the correct exponent (to build a Colossally Abundant Number by prime factorization) for some prime $p$ is$$ \left\lfloor \frac{\log (p^{1 + \delta} - 1) - \log(p^\delta - 1)}{\log p} \right\rfloor \; - \; 1. $$
This is Theorem 10 on page 455 of Alaoglu and Erdos (1944). For a fixed $\delta,$ the exponents either stay the same or decrease for increasing $p,$ and eventually the exponent 0 is reached, so there is your complete number. For a fixed $p,$ the exponent either stays the same or increases with decreasing $\delta.$
I'm not seeing any lists that show $\delta$ and the result, so here, if I call $f(\delta)$ the corresponding colossally abundant number for $\delta,$ I calculate $$ f(1) = 1, \; f(1/2) = 2, \; f(1/4) = 6, \; f(1/6) = 12, \; f(1/10) = 60, \; f(1/12) = 120,$$then$$ f(1/14) = 360, \; f(1/17) = 2520, \; f(1/25) = 5040, \; f(1/31) = 55440, \; f(1/39) = 720720,$$ and so on as $\delta$ decreases.
If you want the first (largest) $\delta$ for which a favorite prime $p$ gets assigned exponent $k,$ let$$ \delta = \frac{\log(p^{k+1} - 1) - \log(p^{k+1} - p)}{\log p} $$
$\endgroup$ 3 $\begingroup$I would suggest trying it backwards: given some $\epsilon >0$, it is easy to find an $N$ such that $\frac{\sigma(n)}{n^{1+\epsilon}} < 3/2^{1+\epsilon}$ for all $n \geq N$ (because $\sigma(n) \leq n\ln{n}+n$).
Then you just optimize $\frac{\sigma(n)}{n^{1+\epsilon}}$ over $2 \leq n \leq N$.
$\endgroup$ 11 $\begingroup$Briggs outlines an approach in his paper Abundant Numbers and the Riemann Hypothesis. Another method would be to multiply the primes found in the integer sequence A073751. Additional methods can be found in the appendix of Schwabhäuser.
$\endgroup$ $\begingroup$jagy@phobeusjunior:~$ ./Colossally_Abundant_construct_deltas 0.01
0.5849625007211564 2 1
0.2223924213364479 2 2
0.0995356735509147 2 3
0.0473057147783566 2 4
0.0230836131130409 2 5
0.0114047632722493 2 6
0.2618595071429147 3 1
0.0728580123298782 3 2
0.0230452619595065 3 3
0.1132827525593782 5 1
0.0203734624179445 5 2
0.0686215613240664 7 1
0.0362865626271021 11 1
0.0288925673866187 13 1
0.0201744121952064 17 1
0.0174203964661791 19 1
0.0135734947947221 23 1
0.0100678863359082 29 1
jagy@phobeusjunior:~$
jagy@phobeusjunior:~$
jagy@phobeusjunior:~$ ./Colossally_Abundant_construct_deltas 0.01 | sort -n -r
0.5849625007211564 2 1
0.2618595071429147 3 1
0.2223924213364479 2 2
0.1132827525593782 5 1
0.0995356735509147 2 3
0.0728580123298782 3 2
0.0686215613240664 7 1
0.0473057147783566 2 4
0.0362865626271021 11 1
0.0288925673866187 13 1
0.0230836131130409 2 5
0.0230452619595065 3 3
0.0203734624179445 5 2
0.0201744121952064 17 1
0.0174203964661791 19 1
0.0135734947947221 23 1
0.0114047632722493 2 6
0.0100678863359082 29 1
jagy@phobeusjunior:~$
jagy@phobeusjunior:~$ =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
#include <iostream>
#include <stdlib.h>
#include <fstream>
#include <strstream>
#include <list>
#include <set>
#include <math.h>
#include <iomanip>
#include <string>
#include <algorithm>
#include <iterator>
#include <gmp.h>
#include <gmpxx.h>
#include "form.h" // after gmp.h and gmpxx.h
using namespace std;
// g++ -o Colossally_Abundant_construct_deltas Colossally_Abundant_construct_deltas.cc -lgmp -lgmpxx
// ./Colossally_Abundant_construct_deltas
// save in temp.txt then
// sort -n -r temp.txt > Colossally_Abundant_Deltas.txt
int main(int argc, char *argv[])
{ if ( argc != 2) cout << "Usage: ./Colossally_Abundant_construct_deltas LowerBound " << endl; else { double bound = 0.5 ; bound = atof(argv[1]); int goon = 1; for (mpz_class p = 2; goon && p < 100100; p += 1) { if( mp_PrimeQ(p) ) { mpz_class q = p; double eps = 1.0; for (int k = 1; k <= 500 && eps > bound; ++k) { q *= p; double mu = mp_Log( q - 1 ) ; mu -= mp_Log( q - p ) ; mu /= mp_Log( p); cout.precision(16); cout.setf(ios::fixed, ios::floatfield); // DD page 582 if ( mu > bound) cout << mu << setw(12) << p << setw(12) << k << endl; eps = mu; goon = ( k > 1 ) || (mu >= bound); } // for k } // if prime }// for p } // else argc return 0 ;
}jagy@phobeusjunior:~$ jagy@phobeusjunior:~$
jagy@phobeusjunior:~$ ./Colossally_Abundant_construct_deltas 0.001 > temp.txt
jagy@phobeusjunior:~$ sort -n -r temp.txt > Colossally_Abundant_Deltas.txt
jagy@phobeusjunior:~$ cat Colossally_Abundant_Deltas.txt
0.5849625007211564 2 1
0.2618595071429147 3 1
0.2223924213364479 2 2..........and so on ..........
Compare output below with
which comes from
1 2 2 log ten: 0.30103 2 3 6 log ten: 0.778151 3 2 12 log ten: 1.07918 4 5 60 log ten: 1.77815 5 2 120 log ten: 2.07918 6 3 360 log ten: 2.5563 7 7 2520 log ten: 3.4014 8 2 5040 log ten: 3.70243 9 11 55440 log ten: 4.74382 10 13 720720 log ten: 5.85777 11 2 1441440 log ten: 6.1588 12 3 4324320 log ten: 6.63592 13 5 21621600 log ten: 7.33489 14 17 367567200 log ten: 8.56534 15 19 6983776800 log ten: 9.84409 16 23 160626866400 log ten: 11.2058 17 2 321253732800 log ten: 11.5068 18 29 9316358251200 log ten: 12.9692 19 31 288807105787200 log ten: 14.4606 20 7 2021649740510400 log ten: 15.3057 21 3 6064949221531200 log ten: 15.7828 22 37 224403121196654400 log ten: 17.351 23 41 9200527969062830400 log ten: 18.9638 24 43 395622702669701707200 log ten: 20.5973 25 2 791245405339403414400 log ten: 20.8983 26 47 37188534050951960476800 log ten: 22.5704 27 53 1970992304700453905270400 log ten: 24.2947 28 59 116288545977326780410953600 log ten: 26.0655 29 5 581442729886633902054768000 log ten: 26.7645 30 61 35468006523084668025340848000 log ten: 28.5498 31 67 2376356437046672757697836816000 log ten: 30.3759 32 71 168721307030313765796546413936000 log ten: 32.2272 33 73 12316655413212904903147888217328000 log ten: 34.0905 34 11 135483209545341953934626770390608000 log ten: 35.1319 35 79 10703173554082014360835514860858032000 log ten: 37.0295=====================
$\endgroup$
