Project Euler Forum

Posted: **Fri Apr 27, 2012 4:40 am**

Hi I am having some computation issues with problem 381.
So let's say I want to calculate S(7): this is 6!+5!+4!+3!+2! mod 7 = 6!mod7 + 5!mod7 + 4!mod7 + 3!mod7 + 2!mod7 mod 7 = 6+1+3+6+2 mod 7 = 4.

Due to Wilson's theorem I can deduce that for any prime p S(P) = (P-3)!modP+(P-4)!modP+(P-5)!modP mod P... So the first 2 factorials are trivial when calculating them mod P as (P-1)! mod P = P-1 and (P-2)! mod P = P-1/P-1 = 1 mod P.

However the last three factorials are expensive to compute. Obviously computing (P-5)!modP would be sufficient, as the other two factorials can be deduced from that, but (P-5)! is very expensive. So I try to compute (P-3)!modP from (P-2)!modP so
(P-3)! mod P = x
where x can be solved from: x*(P-2) = 1 mod P
however this cannot be solved straightforward (at least that I am aware of) so I have to test every single value for x until the equation holds. This may be a total of P multiplications which have to be repeated for (P-4)! and (P-5)! and as P limits 10^8, this is extremely slow.

Am I on the right track? Any other ideas?? Am I right that the number of primes below 10^8 end in 455?

Thank you!

Posted: **Fri Apr 27, 2012 6:17 am**

Nevermind I solved it already

For those of you out there that are interested, I was on the right track but solving x*(P-2) = 1 mod P by trying different values for X is not efficient. There is another way to solve this equation (as I gave already some tips, I will not say what the method it ^^).

execution took for me about 3 minutes which is not too bad on dualcore 1.6 GHz laptop

And it is correct that the number of prime numbers under 10^8 ends in 455

Posted: **Fri May 04, 2012 12:15 am**

is testing codition for 5-100 correct? I allwys get result as 489

python code (whitout any spoiler)

Code: Select all

import math
def sfunc(a):
    return sum(math.factorial(a-i) for i in range(1,6))%a
 
print(sum(sfunc(i) for i in range(5,100)))

Posted: **Fri May 04, 2012 1:10 am**

ralu wrote:is testing codition for 5-100 correct?

Yes, it really is 480.

Posted: **Fri May 04, 2012 1:21 am**

is it impropper to ask what is wrong whit my code in prevous post?

Posted: **Fri May 04, 2012 2:01 am**

Try the 3rd word of the problem statement

Posted: **Fri May 04, 2012 2:03 am**

How dumb i was.

Thanx

Posted: **Wed Aug 01, 2018 12:44 am**

I'm getting an answer, but it's not correct. However I'm able to produce the correct number when p < 10^2. Can someone confirm if the next few powers of 10 are correct?

p<10^3 =
p<10^4 = [removed by moderator]
p<10^5 =

Posted: **Wed Aug 01, 2018 8:12 am**

enigmaticcam wrote: Wed Aug 01, 2018 12:44 am I'm getting an answer, but it's not correct. However I'm able to produce the correct number when p < 10^2. Can someone confirm if the next few powers of 10 are correct?

I've removed your values from public view, but I can confirm that they were all correct.

Posted: **Wed Aug 01, 2018 6:10 pm**

Thank you! That was what I needed. I was multiplying too high and went above a 64-bit number. Fixed and solved

Project Euler Forum

Problem 381

Problem 381

Re: Problem 381

Re: Problem 381

Re: Problem 381

Re: Problem 381

Re: Problem 381

Re: Problem 381

Re: Problem 381

Re: Problem 381

Re: Problem 381