Grind Report 4

I was looking through the problems on Project Euler and saw this problem and ended up solving it.

Problem 5

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

*WARNING: This contains the solution!*

This was a very easy problem for me. Having just done that factoring problem the other day, my immediate thought was "What does this [2520] factor down to?"

1-10 Factor Solution: 2 * 2 * 2 * 3 * 3 * 5 * 7 or 2^3 * 3^2 * 5 * 7

Notice anything about this? Every number from 1 to 10 can be made from these numbers. Getting a little more in depth.

Given a range 1-k (this problem k=20) for every prime number, n, between that range include n^m in the solution. m is the nth root of k. floor m, because m is integral.

Trying that on the 1-10 factor.

k=10

n=2
k^1/2 = 3.1622
floor(3.1622) = 3
so include 2^3 in the solution.

n=3
k^1/3 = 2.1544
m = floor(2.1544) = 2
include 3^2

n=5
k^1/5 = 1.5848
m = floor(1.5848) = 1
include 5^1

Once we find a prime number that has m = 1, we can assume that for all remaining n up to k, m = 1.

i.e.
n = 7
m = 1

So without any programming I put together the problem's solution.

2 * 2 * 2 * 2 * 3 * 3 * 5 * 7 * 11 * 13 * 17 * 19 =
2^4 * 3 ^2 * 5^1 * 7^1 * 11^1 * 13^1 * 17^1 * 19^1

Pretty cool huh!?

With this little theory I put together it would be pretty easy to program this to solve for any range 1-k. I may come back to do it but for now I have family plans :)

*saved game*