Ask Professor Puzzler
Do you have a question you would like to ask Professor Puzzler? Click here to ask your question!
Judah asks: "A Highly Composite number is a number that has more factors than any other less than it (positive, whole numbers). Like 12 has 6 factors, which is more than any other below it (whereas 1 has 1 , 2 has 2, and so on). Is there an equation to tell if a number is highly composite? If no, than I might find one. :P But is there?"
I'm not familiar with an actual formula that you could use (something along the lines of a function that you plug n into it and you get the nth highly composite number out). However, there are some tips I can give you for finding highly composite numbers (short of looking up a list on a website somewhere).
First, it's important to note that what really matters in highly composite numbers is the exponents in their prime factorization. Why? Because the number of factors a number has can be directly calculated from those exponents. Let me show you how.
Take the number 72. How many factors does this number have? We can find out by simply testing numbers to find out if they're factors:
1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72
72 has twelve factors.
But there's another way to find out how many factors 72 has. Write the prime factorization of 72:
72 = 2332
Now consider the fact that every factor of 72 contains both powers of 2 and powers of 3. For example, 12 = 2231, 18 = 2·32. This is also true of 1, though you might not think so at first: 1 = 2030. Similiarly, 8 = 2330.
But, of course, if a number has 24 or 33 as part of its prime factoriztion, the number can't be a factor of 72, because it has too many twos, or too many threes.
We can look at it this way: if a number is a factor of 72, it contains in its prime factorization either 20, 21, 22, or 23. Similarly, the prime factorization contains 30, 31, or 32.
There are 4 ways to choose how many twos to include, and 3 ways to choose how many threes to include to build a factor of 72. If you've studied counting principles at all, you know that the total number of ways to create a factor is then 4 x 3 = 12, which matches the number we obtained by listing factors.
Let's try another example: How many factors does 6,615 have? I'm sure you don't want to try to list them all by hand, right? So let's try our other method. Prime factorization of 6615 = 335172.
Thus, there are 4 ways to choose how many threes, 2 ways to choose how many fives, and 3 ways to choose how many sevens to include in a factor. Therefore, there are 4 x 2 x 3 = 24 factors.
So how do we use this to help us find highly composite numbers? Well, we can use it indirectly, because we can use this to help find the smallest number that has n factors.
Let's say we want to find the smallest number with 15 factors. Well, 15 can be factored in two ways:
15 = 15 x 1
15 = 3 x 5
Using the first factorization is going to result in a ridiculously large number (21430), so should use the other way of factoring. We need to have a prime factorization that includes an exponent of 2 and an exponent of 4 (2 is one less than 3, and 4 is one less than 5). We'll get our smallest number by assigning the largest exponent to the smallest prime factor, which gives us 2432 = 144. 144 is the smallest number with 15 factors.
What if we wanted to find the smallest number with 16 factors? There are many more possibilities here, because 16 can be factored in several different ways:
16 = 16 x 1 16 = 8 x 2 16 = 4 x 4 16 = 4 x 2 x 2 16 = 2 x 2 x 2 x 2
Each of these gives rise to a different number:
16 = 16 x 1 21530 = 32768 16 = 8 x 2 2731 = 384 16 = 4 x 4 2333 = 216 16 = 4 x 2 x 2 233151 = 120 16 = 2 x 2 x 2 x 2 21315171 = 210
Of these 120 is the smallest, so 120 is the smallest number with 16 factors.
Notice that the smallest number with 16 factors is actually smaller than the smallest number with 15 factors, which means there is no highly composite number with 15 factors. You can't assume that 120 is a highly composite number, either, until you've done some more testing, but if I had to make a guess, I'd say it probably is. Okay, I just checked a list on Wikipedia, and 120 is a highly composite number.
Hopefully this will inspire you to more exploration, and maybe you'll find that formula you were looking for. Thanks for asking!