## Problem 381

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.

This forum is NOT meant to discuss solution methods for a problem.

In particular don't post any code fragments or results.

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one

Don't post any spoilers
hvdboorn
Posts: 5
Joined: Fri Apr 27, 2012 1:01 am

### Problem 381

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
Posts: 5
Joined: Fri Apr 27, 2012 1:01 am

### Re: Problem 381

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
Posts: 3
Joined: Sat Mar 17, 2012 4:27 pm

### Re: Problem 381

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


Last edited by ralu on Fri May 04, 2012 12:12 am, edited 1 time in total.

jaap
Posts: 525
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

### Re: Problem 381

ralu wrote:is testing codition for 5-100 correct?
Yes, it really is 480.

ralu
Posts: 3
Joined: Sat Mar 17, 2012 4:27 pm

### Re: Problem 381

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

TripleM
Posts: 382
Joined: Fri Sep 12, 2008 2:31 am

### Re: Problem 381

Try the 3rd word of the problem statement

ralu
Posts: 3
Joined: Sat Mar 17, 2012 4:27 pm

### Re: Problem 381

How dumb i was.

Thanx

enigmaticcam
Posts: 10
Joined: Tue Sep 29, 2015 11:07 pm

### Re: Problem 381

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
Posts: 698
Joined: Mon Dec 30, 2013 11:25 pm

### Re: Problem 381

enigmaticcam wrote:
Tue Jul 31, 2018 11:44 pm
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
Posts: 10
Joined: Tue Sep 29, 2015 11:07 pm

### Re: Problem 381

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