Sort 31 Discussions, By:
Please Login in order to post a comment
Guys I spent months trying to solve another challenge (Resilience) in Euler's project by actually making the combinations and sets. But at the end I realized that my numbers are getting bigger and bigger and system just hangs trying to find prime factors for larger numbers.
At the end i figured out that its about finding the properties of the given challenge and coming up with a formula.
For this challenge look at the higher value of n, it is 10^400. so what would be the last element in the main set? its (10^400)^10^400. What on universe is that number?
So there must be a forumula with n and k as its components that gives the result.
Fun fact :
- it is estimated that there are 10^80 atoms in the universe.
- it is estimated that in 2018, there were around 10^22 bytes of data stored
- You can store the number N on around log2(N) bits
Biggest N to be tested is 10^400 ,so N^N is... (10^400)^(10^400).
log2((10^400)^(10^400)) = log2(10) * 400^(10^400) >>>>>> 10^80 * 10^22.
If you planned to actually generate and store that number, I hope you do have a good memory : if every atom of the universe was the entire world's memory, you'd still run out of memory :)
And, in the same way :
There are 2^n-1 subsets of a set of length n.
So if you were to generate 2^(10^400) - 1 numbers... Well, same issue :)
Can somebody help me how to do this ?
I realized following,
1. As k <= 50, only last two digits of n matter, so just calculate (n ^ n)%100, which can be simplified as ((n%100) ^ (n%100)) % 100.
2. But you don't need to do this for all n, as there are only 100 possible values for n % 100.
3. This gives us ~53 numbers which can appear as the last two digits of n^n, and we can easily count how many numbers are there for each such number. The same last digits repeat every 100 numbers.
4. The remaining issue is how many ways can be combine these numbers to get a certain remainder. For example, if K = 3, we count do take any 3 numbers from those numbers who's square ends with 1. But I am not able to extend this to calculate all such combos.
I have the feeling that n power n modulo k is periodic in n, the period being a multiple of k, i.e. there exists M such that (n+Mk)^(n+Mk) = n^n modulo k.
Using this fact, you can infer the distribution of n^n modulo k, without actually computing all the terms, then design an algorithm that's efficient even for a huge n (using careful combinatoric).
But my math is too limited to prove the assertion and find M. A brute force approach is probably doable, as k is small (you search for a period that works for n < 10^5 and hope that it generalizes.
But, frankly, I'm here to do programming, not math, so I won't pursue this route. Good luck to the braves!