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