BMAD 62 Report post Posted March 10, 2014 (edited) An antifirst number is a natural number that has more divisors than any preceding number before it. E.g. 1 has 1 divisor, 2 has 2 divisors, (skip 3 since it only has 2 divisors) 4 has 3 divisors, 6 has 4 divisors, and so on... So the first four numbers are (1,2,4, and 6). Your tasks, find the biggest antifirst number under 1,000,000. Prove or provide a counter example to the following conjecture, all antifirst numbers greater than 6 are abundant or perfect. Edited March 10, 2014 by BMAD 1 1 Share this post Link to post Share on other sites

0 Rainman 14 Report post Posted March 10, 2014 Let n be an integer larger than 1, and let n = p_{1}^{a1}*p_{2}^{a2}*p_{3}^{a3}*...*p_{k}^{ak} be its unique prime factorization with all a_{i} > 0. Lemma 1: n has (a_{1}+1)(a_{2}+1)(a_{3}+1)...(a_{k}+1) divisors. Proof: let d be any divisor of n. We have the unique representation d = p_{1}^{b1}*p_{2}^{b2}*p_{3}^{b3}*...*p_{k}^{bk}, where 0 </= b_{i} </= a_{i} for all i. Conversely, for any sequence of integers {b_{1},b_{2},b_{3},...,b_{k}} such that 0 </= b_{i} </= a_{i}, it represents a unique divisor of n. This bijection shows that the number of divisors equals the number of such sequences. For each i, there are a_{i}+1 ways to select b_{i} between 0 and a_{i} inclusive. Hence the number of such sequences and the number of divisors equals (a_{i}+1)(a_{2}+1)(a_{3}+1)...(a_{k}+1). Lemma 2: all antifirst numbers greater than 6 have at least two different prime factors. Proof: suppose n = p^{a} > 6 is antifirst. By lemma 1, it has a+1 divisors. Now n must be the smallest number with a+1 divisors. But 2^{a} also has a+1 divisors, and is definitely not greater than n = p^{a}. So they must be equal: n = 2^{a}. Because n > 6, we have a > 2. Consider the number m = 2^{a-2}*3 = n*3/4. This is smaller than n, and has (a-1)*2 divisors. But since a > 2, we have (a-1)*2 = a+a-2 >/= a+3-2 = a+1. So m has at least as many divisors as n, which contradicts that n is antifirst. Lemma 3: all antifirst numbers greater than 6 are divisible by 6. Proof: let n > 6 be antifirst. If 2 is not a prime factor of n, take the largest prime p_{max} in the factorization of n and replace all instances of p_{max} with 2. You will get a smaller number m with the same number of divisors as n, which is impossible. So 2 is a prime factor of n. There is at least one other prime factor of n, as guaranteed by lemma 2. If 3 is not a prime factor of n, take the largest prime p_{max} in the factorization of n and replace all instances of p_{max} with 3. You will get a smaller number m with the same number of divisors as n, which is impossible. So 3 is also a prime factor of n. Hence n is divisible by 6. Conjecture 2: if n is perfect, then kn is abundant for all k>1. I've proven this in an earlier topic of yours. 6 is perfect, so any greater number which is divisible by 6 is abundant. By lemma 3, all antifirst numbers greater than 6 are abundant. Q.E.D. The largest antifirst number under 1,000,000 seems to be 720,720 = 2^{4}*3^{2}*5*7*11*13, which has 240 divisors. I don't have a good proof for this, so I could be wrong but I'm fairly convinced I got it right. Share this post Link to post Share on other sites

0 BMAD 62 Report post Posted March 10, 2014 Let n be an integer larger than 1, and let n = p_{1}^{a1}*p_{2}^{a2}*p_{3}^{a3}*...*p_{k}^{ak} be its unique prime factorization with all a_{i} > 0. Lemma 1: n has (a_{1}+1)(a_{2}+1)(a_{3}+1)...(a_{k}+1) divisors. Proof: let d be any divisor of n. We have the unique representation d = p_{1}^{b1}*p_{2}^{b2}*p_{3}^{b3}*...*p_{k}^{bk}, where 0 </= b_{i} </= a_{i} for all i. Conversely, for any sequence of integers {b_{1},b_{2},b_{3},...,b_{k}} such that 0 </= b_{i} </= a_{i}, it represents a unique divisor of n. This bijection shows that the number of divisors equals the number of such sequences. For each i, there are a_{i}+1 ways to select b_{i} between 0 and a_{i} inclusive. Hence the number of such sequences and the number of divisors equals (a_{i}+1)(a_{2}+1)(a_{3}+1)...(a_{k}+1). Lemma 2: all antifirst numbers greater than 6 have at least two different prime factors. Proof: suppose n = p^{a} > 6 is antifirst. By lemma 1, it has a+1 divisors. Now n must be the smallest number with a+1 divisors. But 2^{a} also has a+1 divisors, and is definitely not greater than n = p^{a}. So they must be equal: n = 2^{a}. Because n > 6, we have a > 2. Consider the number m = 2^{a-2}*3 = n*3/4. This is smaller than n, and has (a-1)*2 divisors. But since a > 2, we have (a-1)*2 = a+a-2 >/= a+3-2 = a+1. So m has at least as many divisors as n, which contradicts that n is antifirst. Lemma 3: all antifirst numbers greater than 6 are divisible by 6. Proof: let n > 6 be antifirst. If 2 is not a prime factor of n, take the largest prime p_{max} in the factorization of n and replace all instances of p_{max} with 2. You will get a smaller number m with the same number of divisors as n, which is impossible. So 2 is a prime factor of n. There is at least one other prime factor of n, as guaranteed by lemma 2. If 3 is not a prime factor of n, take the largest prime p_{max} in the factorization of n and replace all instances of p_{max} with 3. You will get a smaller number m with the same number of divisors as n, which is impossible. So 3 is also a prime factor of n. Hence n is divisible by 6. Conjecture 2: if n is perfect, then kn is abundant for all k>1. I've proven this in an earlier topic of yours. 6 is perfect, so any greater number which is divisible by 6 is abundant. By lemma 3, all antifirst numbers greater than 6 are abundant. Q.E.D. The largest antifirst number under 1,000,000 seems to be 720,720 = 2^{4}*3^{2}*5*7*11*13, which has 240 divisors. I don't have a good proof for this, so I could be wrong but I'm fairly convinced I got it right. very well done Rainman. For the proof to the last part that you mentioned, the combinations of the ten numbers you found and see if that derives the 240, in other words, is there a connection between the amount of divisors of a number and its prime factorization? If there is, can we we have greater than 10 factors in a number under 1,000,000 that gives >240 unique divisors? Share this post Link to post Share on other sites

An antifirst number is a natural number that has more divisors than any preceding number before it.

E.g.

1 has 1 divisor,

2 has 2 divisors, (skip 3 since it only has 2 divisors)

4 has 3 divisors,

6 has 4 divisors, and so on...

So the first four numbers are (1,2,4, and 6).

Your tasks,

find the biggest antifirst number under 1,000,000.

Prove or provide a counter example to the following conjecture, all antifirst numbers greater than 6 are abundant or perfect.

Edited by BMAD## Share this post

## Link to post

## Share on other sites