Multiple Personality NumbersDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/