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 
the correct answer.

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 
answer? Can you please explain?

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/