Hello @all,
Now that exams are more or less behind my back (at least, until January), I have decided I would return to Project Euler to learn a new language (I’ve chosen Haskell, as some of you might know) and to improve my very deficient Mathematics skills.
I am tackling problem 160, as it seems to be a problem where my biggest troubles come together:
- I know the concepts involved;
- I think I have a decent idea on how to approach it in a naive way;
- I try to improve the naive way a bit and I get stuck;
As I got stuck, I have decided I would expose my main ideas here and would ask for some help!
For reference, the link is as follows: Project Euler Problem 160.
As we only want to find the last 5 digits before the trailing zeroes, it becomes obvious that we need only to multiply the numbers without the factors which will give origin to the trailing zeroes, i.e., without the 10s, so, we can think on decomposing all the numbers in products involving factors of 2 and/or 5, and group them together to remove the trailing zeroes (as we have seen thanks to an alike problem here, the number of factors of 5 will determine the number of trailing zeroes, as there are way more numbers which have 2 as a factor, but, not 5, so the 10s are “bounded above” by the number of 5s).
We can even exemplify such case for the number 20! :
2 - 2
3 - 3
4 - 2*2
5 - 5
6 - 2*3
7 - 7
8 - 2*4
9 - 3*3
10 - 2*5
11 - 11
12 - 2*6
13 - 13
14 - 2*7
15 - 3*5
16 - 2*8
17 - 17
18 - 2*9
19 - 19
20 - 2*10
Now, if we multiply all the numbers which aren’t striked, we get:
3*4*6*7*8*9*11*12*13*14*3*16*17*9*19*2 = 243290200817664
which is exactly the value of 20! but, without the trailing zeroes.
However, this approach is useless for any numbers maybe around the value of 10^5 / 10^6, let alone the value of 10^12.
I feel that there might be some more properties which can be exploited though, here they are:
- We never cross out any prime numbers other than 2 or 5.
- We always need to “decompose” numbers in their “complementary factors” (this was an invented name) of 2 and/or 5.
- The numbers in the factorial product definition share many factors.
After attempting to play with this a little bit more and taking the above observations into account, I think I have somehow reduced the original problem to an “almost-closed” formula:
If I want the answer for N, here’s what I did:
After factorizing only N, I came up with the following ideas:
Answer is:
((sqrt(floor(N)))^2 * (All primes < N besides 2 and/or 5) * (All numbers < N with factors of 2) * (All numbers < N with factors of 5) ) % 100000
Of course we would need to watch out for repetitions, numbers with multiple factors of 2/5 and all that, but, I really can’t go much further than this…
Any tips would be appreciated.
Best,
Bruno