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

Multiple Personality Numbers

```
Date: 03/13/97 at 02:33:36
From: Anonymous
Subject: Numbers with multiple personalities

The rectangular personalities of a number N are the rectangular arrays
that can be formed from N dots. For example, the number 4 has one
such array as does the number 6.  12 has 2 arrays. We assume that the
2 x 3 array is the same as the 3 x 2 array because one can be derived
from a simple rotation of the figure.  Also, the number 2 has no
arrays because it is considered a linear array.

Of all the numbers less than 1 million, which has the most rectangular
personalities and why?

I would be very grateful if you could help me with this troubling
question.
```

```
Date: 03/13/97 at 12:35:29
From: Doctor Rob
Subject: Re: Numbers with multiple personalities

The question you ask is a very interesting one.  It has to do with
factoring integers into primes.

A prime number is an integer greater than 1 such that it cannot be
written as the product of two smaller integers.  The smallest prime
numbers are 2, 3, 5, 7, 11, 13, 17, and 19.  Other integers greater
than 1 which can be written as the product of two smaller integers are
called composite.  The two smaller integers are called factors or
divisors of the composite number.

Your question can be rephrased as, "Which composite number has the
most divisors?"

There is a very famous and important theorem which says that every
positive integer can be written uniquely (up to order) as a product of
powers of prime numbers.  This is called the Fundamental Theorem of
Arithmetic.

If n = p(1)^e(1) * p(2)^e(2) * ... * p(k)^e(k)

where the p(i)'s are prime numbers, the e(k)'s are positive integers,
and k is a positive integer, then the number of divisors, including
1 and n, is given by the formula:

d = [e(1)+1]*[e(2)+1]*...*[e(k)+1]

(You can see this is true because every divisor of n will have its
unique prime-power factorization involving the same prime numbers
as appear for n, and their exponents cannot be larger than the ones
appearing for n. As a result, the exponent of p(1) can be any number
from 0 to e(1), or e(1)+1 possibilities. Likewise for p(2), ...,
p(k).)

Now the question is, for what primes and exponents can we have the
two conditions n less than or equal to 1000000 and d maximal?

We can assume that p(1) = 2, p(2) = 3, p(3) = 5, and so on.  We can
also assume that e(1) >= e(2) >= e(3), etc.

If k = 1 and p(1) = 2, we can get e(1) = 19 and n = 2^19 = 524288,
for which d = 20.  Larger values of p(1) give smaller values of e(1),
and so smaller values of d, so this is the best we can do for k = 1.

For k = 2, we can get (by trying each e(2) value):

e(1) = 18,  e(2) =  1,  n = 2^18*3   = 786432,  d = 38
e(1) = 16,  e(2) =  2,  n = 2^16*3^2 = 589824,  d = 51
e(1) = 15,  e(2) =  3,  n = 2^15*3^3 = 884736,  d = 64
e(1) = 13,  e(2) =  4,  n = 2^13*3^4 = 663552,  d = 70
e(1) = 12,  e(2) =  5,  n = 2^12*3^5 = 995328,  d = 78
e(1) = 10,  e(2) =  6,  n = 2^10*3^6 = 746496,  d = 77
e(1) =  8,  e(2) =  7,  n = 2^8*3^7  = 559872,  d = 72

The best we can do for k = 2 is 995328, with d = 78.

For k = 3, we can get (by trying each e(3) value):

e(3) = 1,  e(2) =  1,  e(1) = 16,  n = 2^16*3*5     = 983040,  d =  68
e(2) = 2,  e(1) = 14,  n = 2^14*3^2*5   = 737280,  d =  90
e(2) = 3,  e(1) = 12,  n = 2^13*3^3*5   = 552960,  d = 104
e(2) = 4,  e(1) = 11,  n = 2^11*3^4*5   = 829440,  d = 120
e(2) = 5,  e(1) =  9,  n = 2^9*3^5*5    = 622080,  d = 120
e(2) = 6,  e(1) =  8,  n = 2^8*3^6*5    = 933120,  d = 126
e(3) = 2,  e(2) =  2,  e(1) = 12,  n = 2^12*3^2*5^2 = 921600,  d = 117
e(2) = 3,  e(1) = 10,  n = 2^10*3^3*5^2 = 691200,  d = 132
e(2) = 4,  e(1) =  8,  n = 2^8*3^4*5^2  = 518400,  d = 135
e(2) = 5,  e(1) =  7,  n = 2^7*3^5*5^2  = 777600,  d = 144
e(3) = 3,  e(2) =  3,  e(1) =  8,  n = 2^8*3^3*5^3  = 864000,  d = 144
e(2) = 4,  e(1) =  6,  n = 2^6*3^4*5^3  = 648000,  d = 140
e(2) = 5,  e(1) =  5,  n = 2^5*3^5*5^3  = 972000,  d = 144
e(3) = 4,  e(2) =  4,  e(1) =  4,  n = 2^4*3^4*5^4  = 810000,  d = 125

The best we can do for k = 4 is 777600, 864000, or 972000, with
d = 144.

For k = 4, we can get:

e(4)  e(3)  e(2)  e(1)          n                  d
1     1     1    13   2^13*3*5*7      = 860160  112
1     1     2    11   2^11*3^2*5*7    = 645120  144
1     1     3    10   2^10^3^3*5*7    = 987680  176
1     1     4     8   2^8*3^4*5*7     = 725760  180
1     1     5     6   2^6*3^5*5*7     = 544320  168
1     2     2     9   2^9*3^2*5^2*7   = 806400  180
1     2     3     7   2^7*3^3*5^2*7   = 604800  192
1     2     4     6   2^6*3^4*5^2*7   = 907200  210
1     3     3     5   2^5*3^3^5^3*7   = 756000  192
2     2     2     6   2^6*3^2*5^2*7^2 = 705600  189
2     2     3     4   2^4*3^3*5^2*7^2 = 529200  180

The best we can do for k = 4 is 907200 with d = 210

For k = 5, we can get:

e(5)  e(4)  e(3)  e(2)  e(1)            n                   d
1     1     1     1     9   2^9*3*5*7*11       = 591360  160
1     1     1     2     8   2^8*3^2*5*7*11     = 887040  216
1     1     1     3     6   2^6*3^3*5*7*11     = 665280  224
1     1     1     4     5   2^5*3^4*5*7*11     = 997920  240
1     1     2     2     5   2^5*3^2*5^2*7*11   = 554400  216
1     1     2     3     4   2^4*3^3*5^2*7*11   = 831600  240
1     2     2     2     3   2^3*3^2*5^2*7^2*11 = 970200  216

The best we can do for k = 5 is 997920 or 831600 with d = 240

For k = 6, we can get:

e(6)  e(5)  e(4)  e(3)  e(2)  e(1)            n                      d
1     1     1     1     1     6                                  224
1     1     1     1     2     4           720720                 240
1     1     1     2     2     2                                  216

The best we can do for k=6 is also d = 240, n = 720720.

You can do k = 7.

I hope this helps.

-Doctor Rob,  The Math Forum
Check out our web site!  http://mathforum.org/dr.math/
```

```
Date: 03/16/97 at 04:07:12
From: Anonymous
Subject: Numbers with multiple personalities

Dear Dr Math,

Your answer was very easy to understand, but I have one question.
You worked out the number of divisors the number had and not the
number of rectangular arrays, so how can I convert your answer?  You
said that 997920, 831600 and 720720 all had the greatest number of
divisors (240), but how many rectangular arrays do they have?

Thank you kindly.
```

```
Date: 03/16/97 at 19:35:37
From: Doctor Rob
Subject: Re: Numbers with multiple personalities

One less than half the number of divisors is the number of rectangular
arrays.  That is because if a is a divisor of n, then there is a b
such that a*b = n, so n objects can be arranged in a rectangular array
that is a-by-b. Of course, then they can also be arranged in an array
that is b-by-a. This means that two different divisors represent the
same array, so that the number of divisors must be double the number
of arrays. But this is not quite right, because 1*n = n, representing
the two divisors 1 and n, which is not being counted as a rectangular
array, so we have to subtract one from half the number of divisors.
This is still not quite right, because some numbers (perfect squares)
can be written as n = a*a, corresponding to a square array a-by-a, but
only corresponding to a single divisor of n, namely a.  If we use the
rule in the first sentence of this paragraph, we will get an answer
that is not an integer, because the number of divisors will be odd, so
half it will not be an integer. In this case, just round up to get

You apply this to your cases.

-Doctor Rob,  The Math Forum
Check out our web site!  http://mathforum.org/dr.math/
```

```
Date: 07/11/2001 at 23:30:44
From: Karinny
Subject: Rectangular personalities

Hi! I still don't understand this problem. Is there any other way to
```

```
Date: 07/12/2001 at 12:10:41
From: Doctor Jaffee
Subject: Re: Rectangular personalities

Hi Karinny,

The explanation was quite thorough. Let's take a look at it together.

The first important point that Dr. Rob made was that the number of
rectangular arrays that can be formed depends upon the number of divisors
that the number has.  For example the divisors of 6 are 1,2,3,6, and if
you express 6 as a product of pairs of them, you get 1 x 6, 6 x 1, 2 x 3,
3 x 2. We have to discard any product that has a 1 in it because that is
considered a linear array.  Furthermore, 2 x 3 and 3 x 2 are just
rotations of each other.  Our conclusion is that 6 has only 1 rectangular
personality.

30, on the other hand has 3 rectangular personalities: 2 x 15, 3 x 10,
and 5 x 6.

The second important point that Dr. Rob presented was the formula from number
theory that determines the number of divisors a number has.  When you
represent a number as the product of powers of primes, then the number of
divisors is the product of each 1 more than each of the exponents; that is,
(e1 + 1)(e2 + 2)(e3 + 3)...(ek + 1)

The formula says n = p1^(e1)*p2^(e2)*p3^(e3)...pk^(ek), where each p
represents a distinct prime number and each e is the corresponding exponent.

For example  (2^3)(3^4)(5)(7) = 22,680

The exponents are 3,4,1, and 1, so the number of divisors, according to the
formula is (3 + 1)(4 + 1)(1 + 1)(1 + 1) = 80.

Now, if you pick any pair of numbers whose product is 22,680 such as 2 and
11,340, you have 2 divisors but only 1 product. Therefore, the number of
rectangular arrays is 1/2 of 80, or 40.  But one of those (1 x 22,680)
doesn't count so there are really only 39.

So, what it comes down to is that we are looking for a number that has a lot
of prime factors, but we are also looking for a number for which the prime
factors have the largest possible exponents. These two goals work against
each other because of the restriction that the product cannot exceed
1,000,000, so we have to find a compromise to satisfy our needs.

Now, if you look at Dr. Rob's computations, you will see that in the case
where he had the product of powers of 5 prime numbers (k = 5), he came up
with the number 997,920 having 240 divisors. If you divide that by 2 to
compensate for the rotation, then subtract 1 to compensate for the product
in which the number 1 is a factor, you get 119 rectangular personalities.

For k = 6, the best he could do was 720,720 also having 119 rectangular
personalities.

Then he suggested to the person who sent in the problem that he or she try
k = 7.

I hope my response helps you to understand Dr. Rob's explanation  a little
better.  Try letting k = 7 and see if you can find a number larger than
997,920 that has more than 240 divisors.

Let me know what you found out. If my explanation requires some
clarification or you have other questions, please write back. Thanks for
writing. I've learned a lot working on this problem with you.

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

```
Date: 07/13/2001 at 15:50:45
From: Karinny
Subject: Rectangular personalities

Dr. Jaffee, thank you very much for your explanations, now things are
clearer. But (there is always a but) I still have a question.
You gave me an example with the number 22,680 which = (2^3)(3^4)(5)(7)
That's clear. I know the exponents are 3,4,1,1 and if I apply the
formula, the number of divisors = 80.

You said that if I pick any pair of numbers whose product is 22,680
such as 2 and 11,340 I will get 2 divisors but only one product. Why?
How? So by just finding the rectangular arrays of 22,680, can I find
the rectangular arrays of all pairs of numbers whose product is 22,680?
Please let me know, I don't know where they got all these problems
from.

Thank you again.
```

```
Date: 07/13/2001 at 17:47:34
From: Doctor Jaffee
Subject: Re: Rectangular personalities

Hi Karinny,

When I said that in the problem 2 x 11,340 = 22,680 there are two divisors,
but only one product, I was referring to the fact that of the 80 different
divisors of 22,680 we know that 2 and 11,340 are two of them.

Since 22,680/2 = 11,340 we have the rectangle whose measurements are
2 x 11,340. Since 22,6800/11,340 = 2, we have the rectangle whose
measurements are 11,340 x 2. But these are the same rectangle rotated
90 degrees.

In other words, for every two divisors whose product is 22,680 there is only
one rectangle.

I hope this clarifies my explanation.  Write back if you want to discuss it
some more.

- Doctor Jaffee, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
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