antifirst

[BMAD]

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

[Rainman]

Let n be an integer larger than 1, and let n = p

₁^a₁*p₂^a₂*p₃^a₃*...*p_k^a_k be its unique prime factorization with all a_i > 0.

Lemma 1: n has (a₁+1)(a₂+1)(a₃+1)...(a_k+1) divisors.

Proof: let d be any divisor of n. We have the unique representation d = p₁^b₁*p₂^b₂*p₃^b₃*...*p_k^b_k, where 0 </= b_i </= a_i for all i. Conversely, for any sequence of integers {b₁,b₂,b₃,...,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₂+1)(a₃+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⁴*3²*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.

[BMAD]

Let n be an integer larger than 1, and let n = p

₁^a₁*p₂^a₂*p₃^a₃*...*p_k^a_k be its unique prime factorization with all a_i > 0.

Lemma 1: n has (a₁+1)(a₂+1)(a₃+1)...(a_k+1) divisors.

Proof: let d be any divisor of n. We have the unique representation d = p₁^b₁*p₂^b₂*p₃^b₃*...*p_k^b_k, where 0 </= b_i </= a_i for all i. Conversely, for any sequence of integers {b₁,b₂,b₃,...,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₂+1)(a₃+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⁴*3²*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?