How to Factorize a Large Number for Permutations?

[Nader AbdlGhani]

Hey guys , Could anyone here tell me the easiest way to solve for n , nP₇ = 604800 , the traditional way (I'm currently using) is to divide 604800 by 10 and then 9 and so on until I get 1 as a result of that division , The problem is this way isn't helpful with all permutations I have in my study , some times it gets tricky .

 

[Mentallic]

Notice that 604,800 is divisible by 100, which means that 10 must be one of the numbers in the factors that multiply to give ^nP_7. This is because we only have one prime factor of 5 which can couple with a prime factor of 2 in various ways, such as from 4 or 6 or 8, and that would give a factor of 10, so the other factor of 10 must be from 10 itself, or even 15 (the factor of 5 coupled with another 2 elsewhere). However, 15*14*...*9 is composed of 7 factors that are all mostly larger than 10, so the result is going to be larger than 10⁷ = 10,000,000 which is much too large. So we only have a few to test, starting at 10*9*...*4 and working our way upwards from there. We actually find that n=10 gives the answer, but if for argument's sake we had to solve, say,

^nP_7=3,991,680

Then we know that n=15 is again too large, but now it's also not divisible by 100 any more, which means we're missing a prime factor of 5, and how can that happen? Only with
12*11*...*6
13*12*...*7
14*13*...*8
n being one larger or smaller than these possibilities and we'd end up with the factor of 5 in 5 or 15 and the result would be divisible by 100. So given just a few values to test, the result should be quick to find.

 

[Nader AbdlGhani]

Notice that 604,800 is divisible by 100, which means that 10 must be one of the numbers in the factors that multiply to give ^nP_7. This is because we only have one prime factor of 5 which can couple with a prime factor of 2 in various ways, such as from 4 or 6 or 8, and that would give a factor of 10, so the other factor of 10 must be from 10 itself, or even 15 (the factor of 5 coupled with another 2 elsewhere). However, 15*14*...*9 is composed of 7 factors that are all mostly larger than 10, so the result is going to be larger than 10⁷ = 10,000,000 which is much too large. So we only have a few to test, starting at 10*9*...*4 and working our way upwards from there. We actually find that n=10 gives the answer, but if for argument's sake we had to solve, say,

^nP_7=3,991,680

Then we know that n=15 is again too large, but now it's also not divisible by 100 any more, which means we're missing a prime factor of 5, and how can that happen? Only with
12*11*...*6
13*12*...*7
14*13*...*8
n being one larger or smaller than these possibilities and we'd end up with the factor of 5 in 5 or 15 and the result would be divisible by 100. So given just a few values to test, the result should be quick to find.

Thanks for your help :D

 

[Mentallic]

Thanks for your help :D

You're welcome!

 

[WWGD]

How about finding the factorization of 604800 as a product of primes? Then divide by 2!, then by 3! , etc.