3
$\begingroup$

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.

  1. @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?
  2. @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$
  • $\begingroup$ What is $\sigma$ here? $\endgroup$ – Jack Crawford Jul 10 at 6:06
  • 1
    $\begingroup$ @JackCrawford $\sigma (n)$ denotes the sum of divisors of $n$. $\endgroup$ – Crostul Jul 10 at 6:08
  • $\begingroup$ I'll modify the question. Apologies. $\endgroup$ – Richard Burke-Ward Jul 10 at 6:19
  • $\begingroup$ @RichardBurke-Ward The Properties sub-section of Wikipedia's Colossally abundant number page says it's based on Grönwall's theorem which says "there is an increasing sequence of integers $n$ such that for these integers $\sigma(n)$ is roughly the same size as $e^{\gamma}n\log(\log(n))$, where $\gamma$ is the Euler–Mascheroni constant". It doesn't give exact details on how to use this, but I believe $n^{\epsilon}$ is compared to $e^{\gamma}n\log(\log(n))$ to determine it's epsilon & some nearby values are checked to confirm. $\endgroup$ – John Omielan Jul 10 at 7:39
  • $\begingroup$ Hi @John. Yes, but I'm not sure how this helps me... $\endgroup$ – Richard Burke-Ward Jul 10 at 10:25
1
$\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$
  • $\begingroup$ I've marked this as answered (sorry @Mindlack, but this answer is more comprehensive; I really appreciate your input, though). But I do have one follow-up question: how are you identifying the values of $\delta$ out of an infinite range of possibilities? $\endgroup$ – Richard Burke-Ward Jul 11 at 10:01
1
$\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$
  • $\begingroup$ Hi @Mindlack. Thanks for this. I have two questions. (1) Can you steer me through the logic that gets you to $3/2^{1+\epsilon}$? (2) Can you point me to a source for the statement $\sigma(n) \le n \ln n+n$? $\endgroup$ – Richard Burke-Ward Jul 10 at 7:56
  • $\begingroup$ $3/2^{1+\epsilon}=\frac{\sigma(n)}{n^{1+\epsilon}}$ for $n=2$. For your second part, write $\frac{\sigma(n)}{n}=\sum_{d|n}{\frac{n/d}{n}} \leq \sum_{1 \leq d \leq n}{d^{-1}} \leq \ln{n}+1$. $\endgroup$ – Mindlack Jul 10 at 8:06
  • $\begingroup$ OK, this is going to take me some time to process... My thinking is not as advanced as yours! Please bear with me. $\endgroup$ – Richard Burke-Ward Jul 10 at 8:28
  • $\begingroup$ Hi again @Mindlack. Can you elaborate? I have no doubt at all that your suggestion is right, but I'm afraid I can't follow the logic. Specifically: (1) are you suggesting by searching for $\frac{\sigma(n)}{n^{1+\epsilon}}<\frac{3}{2^{1+\epsilon}}$ that I search for all $N$ that are not colossally abundant? That's an infinite set! (2) I can't follow the logic in your statement that $\sum_{d|n}\frac{n/d}{n}\le\sum_{1\le d\le n}d^{-1}$ - why is this true? (3) I also can't follow the logic in your statement that $\sum_{1\le d\le n}d^{-1}\le\ln n+1$ - why is this true? $\endgroup$ – Richard Burke-Ward Jul 10 at 9:28
  • $\begingroup$ (1): I suggest that you find an integer $N$ such that for all $n \geq N$, $\frac{\ln{n}+1}{n^{\epsilon}} < 3/2^{1+\epsilon}$ for all $n \geq N$. Yes, it is going to be large, so you have to keep $\epsilon$ not too small. $\endgroup$ – Mindlack Jul 10 at 10:36
1
$\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$
0
$\begingroup$
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
https://oeis.org/A004490/b004490.txt which comes from https://oeis.org/A004490

  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$
-1
$\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 ;
}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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