Project Euler Number 160 - attempt in C

Question

Forgive me if I am being a bit silly, but I have only very recently started programming, and am maybe a little out of my depth doing Problem 160 on Project Euler. I have made some attempts at solving it but it seems that going through 1tn numbers will take too long on any personal computer, so I guess I should be looking into the mathematics to find some short-cuts.

Project Euler Problem 160:

For any N, let f(N) be the last five digits before the trailing zeroes in N!. For example,

9! = 362880 so f(9)=36288 10! = 3628800 so f(10)=36288 20! = 2432902008176640000 so f(20)=17664

Find f(1,000,000,000,000)

New attempt:

#include <stdio.h>


main()
{
    //I have used long long ints everywhere to avoid possible multiplication errors
    long long f; //f is f(1,000,000,000,000)
    f = 1;
    for (long long i = 1; i <= 1000000000000; i = ++i){
        long long p;
        for (p = i; (p % 10) == 0; p = p / 10) //p is i without proceeding zeros
            ;
        p = (p % 1000000); //p is last six nontrivial digits of i
        for (f = f * p; (f % 10) == 0; f = f / 10)
            ;
        f = (f % 1000000); 
    }
    f = (f % 100000);
    printf("f(1,000,000,000,000) = %d\n", f);
}

Old attempt:

#include <stdio.h>

main()
{
    //This part of the programme removes the zeros in factorials by dividing by 10 for each factor of 5, and finds f(1,000,000,000,000) inductively
    long long int f, m; //f is f(n), m is 10^k for each multiple of 5
    short k; //Stores multiplicity of 5 for each multiple of 5
    f = 1;
    for (long long i = 1; i <= 100000000000; ++i){
        if ((i % 5) == 0){
            k = 1;
            for ((m = i / 5); (m % 5) == 0; m = m / 5) //Computes multiplicity of 5 in factorisation of i
                ++k;
            m = 1;
            for (short j = 1; j <= k; ++j) //Computes 10^k
                m = 10 * m;
            f = (((f * i) / m) % 100000);
        }
        else f = ((f * i) % 100000);
    }
    printf("f(1,000,000,000,000) = %d\n", f);
}

Answer 1

It might be an idea to deal with numbers ending 2,4,5,6,8,0 separately. Numbers ending 1,3,7,9 can not contribute to a trailing zeros. Let

A(n) = 1 * 3 * 7 * 9 * 11 * 13 * 17 * 19 * ... * (n-1).
B(n) = 2 * 4 * 5 * 6 * 8 * 10 * 12 * 14 * 15 * 16 * 18 * 20 * ... * n. 

The factorial of n is A(n)*B(n). We can find the last five digits of A(n) quite easily. First find A(100,000) MOD 100,000 we can make this easier by just doing multiplications mod 100,000. Note that A(200,000) MOD 100,000 is just A(100,000)*A(100,000) MOD 100,000 as 100,001 = 1 MOD 100,000 etc. So A(1,000,000,000,000) is just A(100,000)^10,000,000 MOD 100,000.

More care is needed with 2,4,5,6,8,0 you'll need to track when these add a trailing zero. Obviously whenever we multiply by numbers ending 2 or 5 we will end up with a zero. However there are cases when you can get two zeros 25*4 = 100.

Answer 2

I'm not an expert project Euler solver, but some general advice for all Euler problems.

1 - Start by solving the problem in the most obvious way first. This may lead to insights for later attempts

2 - Work the problem for a smaller range. Euler usually give an answer for the smaller range that you can use to check your algorithm

3 - Scale up the problem and work out how the problem will scale, time-wise, as the problem gets bigger

4 - If the solution is going to take longer than a few minutes, it's time to check the algorithm and come up with a better way

5 - Remember that Euler problems always have an answer and rely on a combination of clever programming and clever mathematics

6 - A problem that has been solved by many people cannot be wrong, it's you that's wrong!

I recently solved the phidigital number problem (Euler's site is down, can't look up the number, it's quite recent at time of posting) using exactly these steps. My initial brute-force algorithm was going to take 60 hours, I took a look at the patterns solving to 1,000,000 showed and got the insight to find a solution that took 1.25s.

Answer 3

I would compute the whole thing and then separate first nonzero digits from LSB ... but for you I think is better this:

1.use bigger base

• any number can be rewrite as sum of multiplies of powers of the same number (base)

• like 1234560004587786542 can be rewrite to base b=1000 000 000 like this:

  1*b^2 + 234560004*b^1 + 587786542*b^0
  

2.when you multiply then lower digit is dependent only on lowest digits of multiplied numbers

A*B = (a0*b^0+a1*b^1+...)*(b0*b^0+b1*b^1+...)
     = (a0*b0*b^0)+ (...*b^1) + (...*b^2)+ ...

3.put it together

for (f=1,i=1;i<=N;i++)
 {
 j=i%base;
 // here remove ending zeroes from j
 f*=j;
 // here remove ending zeroes from f
 f%=base;
 }

• do not forget that variable f has to be big enough for base^2
• and base has to be at least 2 digits bigger then 100000 to cover 5 digits and overflows to zero
• base must be power of 10 to preserve decimal digits

[edit1] implementation

uint<2> f,i,j,n,base;   // mine 64bit unsigned ints (i use 32bit compiler/app)
base="10000000000";     // base >= 100000^2 ... must be as string to avoid 32bit trunc
n="20";                 // f(n) ... must be as string to avoid 32bit trunc
for (f=1,i=1;i<=n;i++)
    {
    j=i%base;
    for (;(j)&&((j%10).iszero());j/=10);
    f*=j;
    for (;(f)&&((f%10).iszero());f/=10);
    f%=base;
    }
f%=100000;
int s=f.a[1];           // export low 32bit part of 64bit uint (s is the result)

It is too slow :(

f(1000000)=12544 [17769.414 ms]
f(     20)=17664 [     0.122 ms]
f(     10)=36288 [     0.045 ms]

for more speed or use any fast factorial implementation

[edit2] just few more 32bit n! factorials for testing

this statement is not valid :(

//You could attempt to exploit that 
//f(n) = ( f(n%base) * (f(base)^floor(n/base)) )%base
//do not forget that this is true only if base fulfill the conditions above

luckily this one seems to be true :) but only if (a is much much bigger then b and a%base=0)

g((a+b)!)=g(g(a!)*g(b!))
// g mod base without last zeroes...
// this can speed up things a lot

f(                1)=00001
f(               10)=36288
f(              100)=16864
f(            1,000)=53472
f(           10,000)=79008
f(          100,000)=56096
f(        1,000,000)=12544
f(       10,000,000)=28125

f(        1,000,100)=42016
f(        1,000,100)=g(??????12544*??????16864)=g(??????42016)->42016

• the more is a closer to b the less valid digits there are!!!
• that is why f(1001000) will not work ...

Answer 4

Prod(n->k)(k*a+c) mod a <=> c^k mod a

For example

prod[ 3, 1000003, 2000003,... , 999999000003 ] mod 1000000 

equals

3^(1,000,000,000,000/1,000,000) mod 1000000

And number of trailing 0 in N! equals to number of 5 in factorisation of N!

Answer 5

The problem is:

For any N, let f(N) be the last five digits before the trailing zeroes in N!. Find f(1,000,000,000,000)

Let's rephrase the question:

For any N, let g(N) be the last five digits before the trailing zeroes in N. For any N, let f(N) be g(N!). Find f(1,000,000,000,000).

Now, before you write the code, prove this assertion mathematically:

• For any N > 1, f(N) is equal to g(f(N-1) * g(N))

Note that I have not proved this myself; I might be making a mistake here. (UPDATE: It appears to be wrong! We'll have to give this more thought.) Prove it to your satisfaction. You might want to start by proving some intermediate results, like:

• g(x * y) = g(g(x) * g(y))

And so on.

Once you have obtained a proof of this result, now you have a recurrence relation that you can use to find any f(N), and the numbers you have to deal with don't ever get much larger than N.