GRE Factoring Problem
2012-01-01
What is the smallest non-prime integer that isn't a factor of `20!`?
[Spoiler Below]
Since the solution to this puzzle (let's call it `n`) isn't a factor of `20!`, it must either:
1. Have more of a specific prime in its prime factorization than `20!` does.
2. Have a prime factor that isn't in the prime factorization of `20!`
Let's examine what #1 yields:
since `20! = 20*19*18*17*16*15*14*13*12*11*10*9*8*7*6*5*4*3*2*1`,
we can see 10 even numbers there, so at the very least we would need 11 `2`s in `n`, which is `2^11` which is `2048`, (actually there will be far more `2`s needed ).
if we focused on `3`s, I see 6 multiples of `3`, meaning we'd at least need 7 `3`s in `n`, `3^7` which is `2187`
I see 4 multiples of `5`, so we would need `5^5` which is `3125`
2 multiples of `7`, which would require `7^3` which is `343`
and the smallest prime that only occurs once in `20!` is `11`, which would mean we'd need `11^2`, which is `121`.
so the smallest potential n value we get from this approach is `121`, let's think about #2:
let's choose the smallest prime that isn't a factor of `20!`, to find it we can start with `20` and increment until we get a prime:
`21=3*7`
`22=11*2`
`23` is prime
since `23` is prime, and larger than `20`, it can't be in the prime factorization of `20!`, if that's not clear then look at how we wrote out `20!` above into a product of decreasing integers... each of those integers is less than `20`, therefore none of those integers has `23` as a factor, and therefore the product of all those integers doesn't have `23` in its prime factorization.
but the problem is the find the smallest non-prime non-factor of `20!`, so we need to make it not-prime.
Since `23` is not a factor of `20!` any multiple of 23 will also not be a factor of `20!`, the smallest multiple of `23` which is greater than `23` is `2*23=46`, this is no longer prime, but definitely isn't a factor of `20!`.
this is much better (smaller) than `121`, and therefore must be the solution.
`n` = `46`.
[Spoiler Below]
Since the solution to this puzzle (let's call it `n`) isn't a factor of `20!`, it must either:
1. Have more of a specific prime in its prime factorization than `20!` does.
2. Have a prime factor that isn't in the prime factorization of `20!`
Let's examine what #1 yields:
since `20! = 20*19*18*17*16*15*14*13*12*11*10*9*8*7*6*5*4*3*2*1`,
we can see 10 even numbers there, so at the very least we would need 11 `2`s in `n`, which is `2^11` which is `2048`, (actually there will be far more `2`s needed ).
if we focused on `3`s, I see 6 multiples of `3`, meaning we'd at least need 7 `3`s in `n`, `3^7` which is `2187`
I see 4 multiples of `5`, so we would need `5^5` which is `3125`
2 multiples of `7`, which would require `7^3` which is `343`
and the smallest prime that only occurs once in `20!` is `11`, which would mean we'd need `11^2`, which is `121`.
so the smallest potential n value we get from this approach is `121`, let's think about #2:
let's choose the smallest prime that isn't a factor of `20!`, to find it we can start with `20` and increment until we get a prime:
`21=3*7`
`22=11*2`
`23` is prime
since `23` is prime, and larger than `20`, it can't be in the prime factorization of `20!`, if that's not clear then look at how we wrote out `20!` above into a product of decreasing integers... each of those integers is less than `20`, therefore none of those integers has `23` as a factor, and therefore the product of all those integers doesn't have `23` in its prime factorization.
but the problem is the find the smallest non-prime non-factor of `20!`, so we need to make it not-prime.
Since `23` is not a factor of `20!` any multiple of 23 will also not be a factor of `20!`, the smallest multiple of `23` which is greater than `23` is `2*23=46`, this is no longer prime, but definitely isn't a factor of `20!`.
this is much better (smaller) than `121`, and therefore must be the solution.
`n` = `46`.