Manhattan Challenge Problem

sanjay_dce wrote:another apporach.

total no of possible factors= 144.
total number that has 6 as common factor= 81
so total number of factor that doesn't have 6= 144-81 = 63

Can you explain how you got these numbers?

Vinayak

zuleron wrote:So the primes of 264600 are 2, 2, 2, 3, 3, 3, 5, 5, 7, 7

combinations that don't make 6 are (a) the 2s 5s 7s (b) 3s 5s 7s

(a) 2^3 * 5^2 * 7^2 = 36 combinations
(b) 3^3 * 5^2 * 7^2 = 36 combinations

Can someone please explain how you get 36 combinations from 2^3 * 5^2 * 7^2?

I do not get it .... thanks.

chipbmk wrote:

zuleron wrote:So the primes of 264600 are 2, 2, 2, 3, 3, 3, 5, 5, 7, 7

combinations that don't make 6 are (a) the 2s 5s 7s (b) 3s 5s 7s

(a) 2^3 * 5^2 * 7^2 = 36 combinations
(b) 3^3 * 5^2 * 7^2 = 36 combinations

Can someone please explain how you get 36 combinations from 2^3 * 5^2 * 7^2?

I do not get it .... thanks.

There is a shortcut formula basically to calculate the number of integral factors for a given number,
if a^p * b^q * c^r ... so on ==> then number of integral factors is (p+1)*(q+1)*(r+1)... so on

Here its,
2^3 * 5^2 * 7^2
take the powers alone and add 1,

(3+1) * (2+1) * (2+1) = 36 (This can also be named as combinations)

Same applies for (b) as well.

Hope this helps..!

papgust wrote:

chipbmk wrote:

zuleron wrote:So the primes of 264600 are 2, 2, 2, 3, 3, 3, 5, 5, 7, 7

combinations that don't make 6 are (a) the 2s 5s 7s (b) 3s 5s 7s

(a) 2^3 * 5^2 * 7^2 = 36 combinations
(b) 3^3 * 5^2 * 7^2 = 36 combinations

Can someone please explain how you get 36 combinations from 2^3 * 5^2 * 7^2?

I do not get it .... thanks.

There is a shortcut formula basically to calculate the number of integral factors for a given number,
if a^p * b^q * c^r ... so on ==> then number of integral factors is (p+1)*(q+1)*(r+1)... so on

Here its,
2^3 * 5^2 * 7^2
take the powers alone and add 1,

(3+1) * (2+1) * (2+1) = 36 (This can also be named as combinations)

Same applies for (b) as well.

Hope this helps..!

That is exactly what I was looking for. Thanks for the explanation!

sanjay_dce wrote:another apporach.

total no of possible factors= 144.
total number that has 6 as common factor= 81
so total number of factor that doesn't have 6= 144-81 = 63

Your approach is very interesting and what I like very laconic, unfortunately i didnt understand how you get 81...

the answer is 63
the first set : 5,7,2,2,2 this yields the following set of factors: 5c5+4c5+3c5+2c5+1c5= 6+ 25
the second set without 3 yields, 5,7,3,3,3, again this gives the following factors: 5c5+4c5+3c5+2c5+1c5=2+25
the total is 62 but don't forget 1 which makes 63 in total

Number of factors of 264600 = 144
Number of factors of 264600 that are divisible by 6 = 81

Hence number of factors of 264600 which are not divisible by 6 = 144 - 81 = 63

Folks, here is the detailed explanation. Hope this helps......


[/img]

This is a very good question involving fundamental concepts.

One way to solve the question is to find the no. of multiples of 6 from 264,600 and subtract it from the total no. of factors of the number.
The formula used for this is: if the prime factorization of the number is a^p * b^q * c^r
then the number of factors is given by: (p+1) * (q+1) * (r+1).
Note that they also include the factors a^0, b^0 and c^0.

To find the number of factors that are also multiples of 6, we would therefore need at least 1 two and 1 three to account for six.
So powers of 2: should be at least 1 or greater (exclude 2^0)
Similarly powers of 3: should be at least 1 or greater (exclude 3^0).
--------
For instance: suppose we want to find the factors of 18 that are also multiples of 6.
Prime Factorization of 18: 2^1 * 3^2
So total factors are: (1+1)*(2+1) = 6 (1,2,3,6,9,18)

We have to fetch the factors that are only multiples of 6.
1. Here we need to exclude 2^0 (because if we include 2^0 there will be at least one factor of 18 that's not a multiple of 6, since 2 is excluded from here)
The factors of 18 are: (2^0 2^1) (3^0 3^1 3^2)
: (2^0*3^0),(2^0*3^1),(2^0*3^2),(2^1*3^0),(2^1*3^1),(2^1*3^2)
: 1,3,9,2,6,18

2. For the same reason as above we need to exclude 3^0 too (because if we include 3^0 that will include at least factor that may not be a multiple of 6, since 3 is not there).

Now prime factorization of 264,600: 2^3 * 3^3 * 5^2 * 7^2
Here factors of 264,600 that are multiple of 6 = (3) (3) (2+1) (2+1) = 81
Subtract this from total # of factors: 144-81 = 63 (answer).


Thanks
Prashant

Prashant - Did you realise that you bumped on to a very old thread ?