Antifirst Numbers

Date: 10/23/2000 at 10:53:23
From: Karol
Subject: Antifirst numbers

An antifirst number is a number that has more divisors than all of the 
numbers before it. For example, the first six antifirst numbers are:

     1  It has only one number which divides it (1)
     2  It has two   (1, 2)
     4  It has three (1, 2, 4)
     6  It has four  (1, 2, 3, 6)
    12  It has six   (1, 2, 3, 4, 6, 12)
    24  It has eight (1, 2, 3, 4, 6, 8, 12, 24)

and so on.

I'm a young computer programmer and I need to write a program that 
will calculate the antifirst numbers between 1 and 2,000,000,000. This 
is a huge amount to check and my computer says that it will take 1000 
days (3 years). I need the program to finish within three weeks.

I need to know a formula to check if a number is antifirst or one that 
will calculate these numbers. If you could help me it would be very 
kind of you. Thanks!

Date: 10/23/2000 at 16:58:30
From: Doctor Rob
Subject: Re: Antifirst numbers

Thanks for writing to Ask Dr. Math, Karol.

A better approach than to try 2,000,000,000 numbers is to find the 
smallest numbers with 1, 2, 3, 4, 5, 6, ... divisors. To do this, use 
the formula for the number of divisors of a number in terms of its 
prime power factorization: if

            r
     n = PRODUCT p(i)^e(i)
           i=1

then the number of divisors is

               r
     d(n) = PRODUCT [e(i)+1]
              i=1

For d(n) = 1, you must have e(i) = 0 for all i, so n = 1.

For d(n) = 2, you must have r = 1 and e(1) = 1, so n = p(1). To make 
this as small as possible pick p(1) as small as possible, but prime, 
so p(1) = 2, and n = 2.

For d(n) = 3, you must have r = 1 and e(1) = 2, so n = p(1)^2. To make 
this as small as possible, pick p(1) = 2, so n = 4.

For d(n) = 4, you can have either r = 1 and e(1) = 3, so n = p(1)^3, 
or you can have r = 2 and e(1) = e(2) = 1, so n = p(1)*p(2). In the 
first case the smallest possibility is n = 2^3 = 8, and in the second 
case the smallest is n = 2*3 = 6.

For d(n) = 5, you must have r = 1 and e(1) = 4, so n = p(1)^4. The 
smallest n is then 2^4 = 16.

For d(n) = 6, you can have either r = 1 and e(1) = 5, so n = p(1)^5, 
or you can have r = 2, e(1) = 2, and e(2) = 1, so n = p(1)^2*p(2). In 
the first case, the smallest is n = 2^5 = 32, and in the second case 
the smallest is n = 2^2*3 = 12.

For a general d(n), you have to find all the ways to factor it into 
numbers > 1, let those factors be e(i) + 1, and in each case figure 
out the form of n. Then make the p(i) with the highest exponents be 
the smallest primes, and you will have the smallest number of that 
form. Pick the least of these over all cases, and you will have the 
least n with that value of d(n). For example, with 8, you will have to 
consider 8, 4*2, and 2*2*2, and the minimums are 128, 24, and 30, of 
which the least is 24. For 12, you will have to consider 12, 6*2, 4*3, 
and 3*2*2. For 24, you will have to consider 24, 12*2, 8*3, 6*4, 
6*2*2, 4*3*2, and 3*2*2*2. For 48, there are 12 cases.

Once those smallest values exceed 2,000,000,000 for a long stretch, 
you can stop. This means you don't have to go too high.

Now write down the numbers d(n) in increasing order along with their 
least n's. Throw out those which are larger than some later number, 
and you are done:

     d(n)      1   2   3   4   5   6   7   8   9  10 ...
     least n   1   2   4   6  16  12  64  24 216  80 ...
                              XX      XX     XXX     ...

This should all be pretty fast on a computer, once the program has 
been written.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/