Problem 381

[hvdboorn]

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!

[hvdboorn]

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

[ralu]

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)))

[jaap]

is testing codition for 5-100 correct?

Yes, it really is 480.

[ralu]

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

[TripleM]

Try the 3rd word of the problem statement

[ralu]

How dumb i was.

Thanx

[enigmaticcam]

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 =

[RobertStanforth]

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.

[enigmaticcam]

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