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 2s in n, which is 211 which is 2048, (actually there will be far more 2s needed ).
if we focused on 3s, I see 6 multiples of 3, meaning we'd at least need 7 3s in n, 37 which is 2187
I see 4 multiples of 5, so we would need 55 which is 3125
2 multiples of 7, which would require 73 which is 343
and the smallest prime that only occurs once in 20! is 11, which would mean we'd need 112, 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.
No comments:
Post a Comment