All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
Largest possible value of |S| (Posted on 2024-11-07) Difficulty: 3 of 5
S is a subset of the divisors of 2024^2024 such that no number in S has its own multiple in S.

What is the largest possible value of |S|?

No Solution Yet Submitted by K Sengupta    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Solution Comment 4 of 4 |
In my last comment I looked at triplets of the exponents.  But actually the exponent on 2 is so large compared to 11 and 13 it is better to look at pairs of exponents for 11 and 13.

I will first illustrate with an example of 2024^3
2024^3 = 2^9 * 11^3 ^ 13^3
I can make a total of 16 distinct ordered pairs for the exponents of 11 and 13: (0,0) to (3,3).  Sort them in order of their sums and we will have 7 total classes:
(0,0)
(0,1), (1,0)
(0,2), (1,1), (2,0)
(0,3), (1,2), (2,1), (3,0)
(1,3), (2,2), (3,1)
(2,3), (3,2)
(3,3)

Next I want to add the exponent for 2, and I will do so by putting the larger exponents for 2 with the smaller exponents for 11 and 13.  Then the list looks like
(6,0,0)
(5,0,1), (5,1,0)
(4,0,2), (4,1,1), (4,2,0)
(3,0,3), (3,1,2), (3,2,1), (3,3,0)
(2,1,3), (2,2,2), (2,3,1)
(1,2,3), (1,3,2)
(0,3,3)

Then these sets of exponents now form a set of 16 factors of 2024^3 such that no one of them is a divisor of another.
It is impossible to make this set larger.  Every possible pair of exponents for 11 and 13 is already present If I were to add any other factor, it must have a matching set of exponents for 11 and 13 which means that pair will be multiple of the one or the other by a factor of 2.
So then the answer for 2024^3 is 16, which is (3+1)^2

So now onto the problem as stated. 
2024^2024 = 2^6072 * 11^2024 * 13^2024
Identical setup, just larger.  Then the largest possible value of |S| for the problem as given is (2024+1)^2 = 4100625.

  Posted by Brian Smith on 2024-11-16 11:39:07
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (5)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information