Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
College Number Theory
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search