Project Euler #245: Coresilience

  • + 1 comment

    Clearly, this challenge is more about efficiency, rather than simply getting the result, since most test cases fail because time has run out. I believe any way of computing the the result with an algorithm that relies eventually on factorization is bound to fail as that's not efficient enough. Therefore I started looking at the C(n) function and the values of n that produce a unit fraction. Let's call U the set of those values. The problem is equivalent to sum the elements of U up to a certain value. It's simple to prove that all prime numbers belong to U. It's also not difficult to prove that if n is divisible by p^k with p prime and k>1 then n doesn not belong to U. So the elements of U must be a "simple" product of prime numbers (that is p1p2...pn for primes p1, p2, ...), but unfortunately not all of them! For example 15 is in U, but not 21. Just to give you an idea, there are only six non-prime numbers in U below 1000: 15 = 3x5, 85 = 5x17, 255 = 3x5x17, 259 = 7x37, 391 = 17x23, 589 = 19x31. Thus, if it were not for those "sporadic" non-primes, the problem would be equivalent to computing the pi(n) function (the sum of all prime numbers up to n), for which algorithms that produce the result more efficiently than listing primes or factorize are known. Unfortunately, I do not know an algorithm that take the sporadic non-primes into account.