Thursday, September 25, 2014

Least positive integer with 2014 factors - Detailed Solution

Actual Twitter Problem from 9-23-14 had additional restrictions which didn't fit in the title:

Explain why (3^52)(7^18)(11) is the smallest positive integer with 2014 factors and which doesn't end in 5 or an even digit.

Before the solution, a few
REFLECTIONS...
1) This is not an SAT or typical Common Core Problem. It's more challenging than that. But it does apply a fundamental principle of arithmetic which is often overlooked.
2) The solution below is more detailed than most but these are the kinds of solutions I will be emailing to you when you subscribe. See details at top of sidebar to the right.


Very Very Very Detailed Solution:
There's a fundamental rule about the number of factors of any positive integer > 1. I'll demo it with 12...
Step 1. Prime factorization of 12 is (2^2)•(3^1)
Step 2. Each factor of 12 is then of the form (2^a)(3^b) where a=0,1,2 and b=0,1
Step 3. Using the multiplication principle of counting there are (3)(2)=6 possible combinations of the exponents, each one producing a unique factor of 12:
1=(2^0)(3^0) (0,0) pair
2=(2^1)(3^0) (1,0) pair
3=(2^0)(3^1) (0,1) pair etc...
4=(2^2)(3^0)
6=(2^1)(3^1)
12=(2^2)(3^1)
So think of this as the
"Add 1 to the exponents and multiply" Rule!
Back to 2014 factors...
From Wolfram Alpha (enter "factor 2014")
2014=53•19•2
To construct an integer with this many factors we reverse the previous procedure, I.e., we SUBTRACT 1:
If p1,p2,p3 are different primes then
((p1)^52)•((p2)^18)•((p3)^1) will have
53•19•2 =2014 factors!
From the conditions we want to use the 3 smallest primes excluding 2 and 5, namely 3,7,11:
(3^52)(7^18)(11^1).
QED
(Mathematician's way of saying "I'm done!")

No comments: