• 0

antifirst

Question

Posted (edited) · Report post

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
-1

Share this post


Link to post
Share on other sites

2 answers to this question

  • 0

Posted · Report post

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

1a1*p2a2*p3a3*...*pkak be its unique prime factorization with all ai > 0.

Lemma 1: n has (a1+1)(a2+1)(a3+1)...(ak+1) divisors.

Proof: let d be any divisor of n. We have the unique representation d = p1b1*p2b2*p3b3*...*pkbk, where 0 </= bi </= ai for all i. Conversely, for any sequence of integers {b1,b2,b3,...,bk} such that 0 </= bi </= ai, 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 ai+1 ways to select bi between 0 and ai inclusive. Hence the number of such sequences and the number of divisors equals (ai+1)(a2+1)(a3+1)...(ak+1).

Lemma 2: all antifirst numbers greater than 6 have at least two different prime factors.

Proof: suppose n = pa > 6 is antifirst. By lemma 1, it has a+1 divisors. Now n must be the smallest number with a+1 divisors. But 2a also has a+1 divisors, and is definitely not greater than n = pa. So they must be equal: n = 2a. Because n > 6, we have a > 2. Consider the number m = 2a-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 pmax in the factorization of n and replace all instances of pmax 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 pmax in the factorization of n and replace all instances of pmax 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 = 24*32*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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

1a1*p2a2*p3a3*...*pkak be its unique prime factorization with all ai > 0.

Lemma 1: n has (a1+1)(a2+1)(a3+1)...(ak+1) divisors.

Proof: let d be any divisor of n. We have the unique representation d = p1b1*p2b2*p3b3*...*pkbk, where 0 </= bi </= ai for all i. Conversely, for any sequence of integers {b1,b2,b3,...,bk} such that 0 </= bi </= ai, 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 ai+1 ways to select bi between 0 and ai inclusive. Hence the number of such sequences and the number of divisors equals (ai+1)(a2+1)(a3+1)...(ak+1).

Lemma 2: all antifirst numbers greater than 6 have at least two different prime factors.

Proof: suppose n = pa > 6 is antifirst. By lemma 1, it has a+1 divisors. Now n must be the smallest number with a+1 divisors. But 2a also has a+1 divisors, and is definitely not greater than n = pa. So they must be equal: n = 2a. Because n > 6, we have a > 2. Consider the number m = 2a-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 pmax in the factorization of n and replace all instances of pmax 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 pmax in the factorization of n and replace all instances of pmax 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 = 24*32*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?

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now

  • Recently Browsing   0 members

    No registered users viewing this page.