Is there a fast way to solve this problem?

Darya

Junior Member
Joined
Jan 17, 2020
Messages
154
How many different rectangles have an area of 2400? (sides can only be natural numbers) I'm looking for a quick method to solve this problem (not listing) Thank you!
 
Unless I missed a big announcement, is there still no known way to directly determine the prime factors of a number? Do we still have to test all primes less than or equal to the number's square root?

If we don't have a formula for factoring numbers, then there isn't a "fast" way to determine how many ways there are to make a rectangle of a particular area.
 
Unless I missed a big announcement, is there still no known way to directly determine the prime factors of a number? Do we still have to test all primes less than or equal to the number's square root? If we don't have a formula for factoring numbers, then there isn't a "fast" way to determine how many ways there are to make a rectangle of a particular area.
Mr Bland, I really do not follow your problem with this?
\(\displaystyle 2400=24\times 10^2=2^5\times 3\times 5^2\) that seems fast to me.
That gives \(\displaystyle (6)(2)(3)=36\) divisors. So how many pairs \(\displaystyle (L,W)~?\)
 
… Do we still have to test all primes less than or equal to the number's square root? …
Working with paper and pencil, I employ divisibility rules, too. That allows me to skip dividing by some primes. With 2400, I'd start dividing by 2, until the quotient is odd. Then I'd test for divisibility by 3. As soon as that test fails, I'd continue with 5 (were the dividend to end in 0 or 5); otherwise I'd consider 7, and so on. Eventually, the quotient is 1.

I don't understand pka's comment about "your problem".

\(\;\)
 
Mr Bland, I really do not follow your problem with this?
\(\displaystyle 2400=24\times 10^2=2^5\times 3\times 5^2\) that seems fast to me.
How is that determined? Through what function [MATH]f(x)[/MATH] can you get [MATH][2^5, 3, 5^2] = f(2400)[/MATH]?

Through what function [MATH]f(x)[/MATH] can you get [MATH][198733, 777743] = f(154563199619)[/MATH]?

These must be the same function. If such a function exists, then the original rectangle problem can be solved in polynomial time. If such a function exists, cryptosecurity may be in grave peril.
 
How is that determined? Through what function [MATH]f(x)[/MATH] can you get [MATH][2^5, 3, 5^2] = f(2400)[/MATH]?
There is no such function. My I suggest a good course in number theory might help.
 
Factoring is hard (typically), but reasonably easy in this case; counting divisors given the prime factorization is easy, using the method pka used in post #5 without explanation.

Presumably the OP doesn't know that method, so maybe we should explain it, or at least help @Darya discover it, rather than bicker.

So here's the idea: We know that 2400 can be written as [MATH]2^5\times 3\times 5^2[/MATH]. That implies that any divisor can be written as
[MATH]2^a\times 3^b\times 5^c[/MATH], where a is between 0 and 5 (inclusive), b is between 0 and 1, and c is between 0 and 2, respectively.

How many ways can you choose a value for each of a, b, and c?

Then you can think about what that tells us about rectangles. (You'll have to decide whether 2 by 1200 and 1200 by 2 are different rectangles.)
 
There is no such function. My I suggest a good course in number theory might help.
If there is no such function, then the process of finding the combinations of rectangles becomes increasingly convoluted as the target area increases, by merit of the necessity to consider additional potential inputs. As such, there is no "fast" method (in a general sense) to solve this problem.

If you can prove that there is no method for directly resolving the prime factors of a number, then your name will appear in the textbooks forevermore. Curiously, the million-dollar prize isn't offered for counterexamples.
 
Factoring is hard (typically), but reasonably easy in this case; counting divisors given the prime factorization is easy, using the method pka used in post #5 without explanation.

Presumably the OP doesn't know that method, so maybe we should explain it, or at least help @Darya discover it, rather than bicker.

So here's the idea: We know that 2400 can be written as [MATH]2^5\times 3\times 5^2[/MATH]. That implies that any divisor can be written as
[MATH]2^a\times 3^b\times 5^c[/MATH], where a is between 0 and 5 (inclusive), b is between 0 and 1, and c is between 0 and 2, respectively.

How many ways can you choose a value for each of a, b, and c?

Then you can think about what that tells us about rectangles. (You'll have to decide whether 2 by 1200 and 1200 by 2 are different rectangles.)

Thank you for your answer. Maybe I just didn't form a question well enough. What I am curious about is how I can find different pairs of sides when I know how many there are divisors, factorization is obvious.
 
Factoring is hard (typically), but reasonably easy in this case; counting divisors given the prime factorization is easy, using the method pka used in post #5 without explanation.

Presumably the OP doesn't know that method, so maybe we should explain it, or at least help @Darya discover it, rather than bicker.

So here's the idea: We know that 2400 can be written as [MATH]2^5\times 3\times 5^2[/MATH]. That implies that any divisor can be written as
[MATH]2^a\times 3^b\times 5^c[/MATH], where a is between 0 and 5 (inclusive), b is between 0 and 1, and c is between 0 and 2, respectively.

How many ways can you choose a value for each of a, b, and c?

Then you can think about what that tells us about rectangles. (You'll have to decide whether 2 by 1200 and 1200 by 2 are different rectangles.)
nevermind, thank you once again!
 
How is that determined? Through what function [MATH]f(x)[/MATH] can you get [MATH][2^5, 3, 5^2] = f(2400)[/MATH]?

Through what function [MATH]f(x)[/MATH] can you get [MATH][198733, 777743] = f(154563199619)[/MATH]?

These must be the same function. If such a function exists, then the original rectangle problem can be solved in polynomial time. If such a function exists, cryptosecurity may be in grave peril.
By "function" do you mean "formula"? Entirely too many people, trying to solve a math problem, immediately want a "formula" that will do it for them!

The way you solve math problems is by thinking! Looking at "2400" the first thing I see is the "00" on the end which means that \(\displaystyle 100= 10^2= (2(5))^2= 2^25^2\) is a factor. Dividing by 100 leaves 24. I might immediately think "\(\displaystyle 24=6(4)= (3)(2)(4)= 2^3(4)\) or I might think "24= 3(8)" to get the same thing. Or if I didn't happen to see that, I might use "brute strength": 24 is even so divisible by 2; 24/2= 12 which is even so divisible by 2; 12/2= 6, 6/2= 3.

In any case \(\displaystyle 2400= 24(100)= (2^3)(3)(2^2)(5^2)= 2^4(3)(5^2)\).
 
Thank you for your answer. Maybe I just didn't form a question well enough. What I am curious about is how I can find different pairs of sides when I know how many there are divisors, factorization is obvious.
So you're saying you already knew how many divisors there are, and wanted to know the number of rectangles? Here you seem to be saying you want to list them (pairs of sides), but in the OP you explicitly did not want to list.

The number of rectangles is half the number of divisors, since they pair up (unless, of course, the number of divisors were odd).
 
Top