Thanks, Solomon, for setting up the contest! Here are some thoughts on my solutions:
A. Taking a difference in the final step, it is enough to compute the number of zeros needed to write down all numbers from 0 to n. To do this, I computed how often the i-th digit is a 0, for all i. This is quite easy: Say n = 12345, then for the 5th digit we get 1235, for the 4th digit we get 123 * 10, for the 3rd digit 12 * 100, for the second digit 1 * 1000. (If a digit is 0, the formula changes slightly.)
B. I used (the logarithm of) Stirling's formula.
C. Up to trailing zeros, we want to compute modulo 1000, so we will first discard all powers of 2 and 5, and fix that in the end. Now for every n > 0, the product of all those numbers in {n, n+1, n+2, ..., n+999} which are coprime to 2 and 5, is independent of n, and is easily checked to be equal to 1. (The independence of n has nothing to do with computing modulo 1000, of course; the value of the product is not always 1, however: e.g., doing this modulo 10, we get -1.) This means that splitting the factorial into chunks of 1000 consecutive numbers, we can ignore all those coprime to 2 and 5.
As gamesorry pointed out, all powers of 5 go into trailing zeros; so we just compute what this power is (using Legendre's formula). The same power of 2 is then also used up for the trailing zeros. The remaining power of 2 must be multiplied with what we had from the first step.
(Finally, to speed up things, I precomputed the values of the first step for multiples of 1,000,000. Then for large numbers one can start off from the greatest multiple of 1000000 which is smaller than the number in question.
D. The problem is easily translated into the problem of finding the binary expression of n-1.
E. Up to some border cases, we need to find the smallest prime factor of n-3. (The border cases are that for 1, 2, 4, 5, 6 there is no solution, and we really want to find the smallest divisor of n within [4, 5, 6, 7, 9, 11, 13, ...] (continue with primes > 13). Finally, we do not want to compute all primes up to 2**31; if no divisor in the above list <= sqrt(n) was found, then n is a prime (or twice a prime, or three times a prime), and we return n (or n//2, n//3, resp.).
@gamesorry: I think this is exactly what you said. If I understand your code correctly, you go on to find all prime divisors though, which is probably what takes too long.
F. I have "sort of" a solution but it clearly does not meet the time requirements.
You can look at the code
here.
Best, Ulrich
. A and D weren't too bad, and I went with an approximation formula for B so it really only feels like I got 2. Even though both B and C both centralized on factorials, I just could not figure out a way to work around C without actually computing the factorial. Failing to solve C and E (unfortunately never got around to F), I think this only made me realize how weak my grasp on number theory is (despite having a degree in mathematics, my classes heavily outweighed probability theory and statistics and I had never taken courses in number theory or abstract algebra, which I do regret).
)
