Thought Process

Another fun problem, I have 2 key functions that perform the following:

1. legendre_factorial(n, p):

   • We can use Legendre's Formula to find how many times a prime factor, p, is present in n!. Let's say this number is e

2. inv_legendre_factorial(p, e):

   • Using a bisection like algorithm, legendre_factorial, to find the minimum n such that n! has e factors of p

For each i = p1^e1 * p2^e2 * ... * pm^em, we only need to worry about max{inv_legendre_factorial(p1, 1234567890*e1), inv_legendre_factorial(p2, 1234567890*e2) , ..., inv_legendre_factorial(pm, 1234567890*em)}, which I will call the largest power factor, which is exactly N(i), as this factor will be the largest factor of the possible n!

Therefore, we only need to find the prime factorisation of each successive i and see if we find a new largest power factor, then that that will be the new N(i)

I give an example of how my algorithm works

I pre-calculate 9! and store its factors in a dictionary for easy access.

1. 9! = {2:7, 3:4, 5:1, 7:1}, largest power factor = inv_legendre_factorial(3, 1234567890*4) = 9876543138

2. i = 10 = {2:1, 5:1}, therefore 10! = {2:8, 3:4, 5:2, 7:1}

   • inv_legendre_factorial(2, 1234567890*8) = 9876543136 < 9876543138

   • inv_legendre_factorial(5, 2*1234567890) = 9876543150 > 9876543138

     1. Therefore, we have a new N(10) = 9876543150

3. i = 11 = {11:1}, therefore 11! = {2:8, 3:4, 5:2, 7:1, 11:1}

   • inv_legendre_factorial(11, 1*1234567890) = 12345678950 > 9876543150  

     1. Therefore we have a new N(11) = 12345678950

4. i = 12 = {2:2, 3:2}, therefore 12! = {2:10, 3:5, 5:2, 7:1, 11:1}

   • inv_legendre_factorial(2, 10*1234567890) = 12345678920 < 12345678950

   • inv_legendre_factorial(3, 5*1234567890) = 12345678918 < 12345678950

   • Therefore, we have no new N(i), therefore N(12) = N(11)

5. etc, etc

Like this we can see S(12) = 9876543150 + 12345678950 + 12345678950 = 34567901050