Problem 381
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.
See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
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 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
See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
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!
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!

Re: Problem 381
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

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

Re: Problem 381
is testing codition for 5-100 correct? I allwys get result as 489
python code (whitout any spoiler)
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.
Re: Problem 381
Yes, it really is 480.ralu wrote:is testing codition for 5-100 correct?
Re: Problem 381
is it impropper to ask what is wrong whit my code in prevous post?
Re: Problem 381
Try the 3rd word of the problem statement 

-
- Posts: 13
- 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 =
p<10^3 =
p<10^4 = [removed by moderator]
p<10^5 =
- RobertStanforth
- Administrator
- Posts: 789
- Joined: Mon Dec 30, 2013 11:25 pm
Re: Problem 381
I've removed your values from public view, but I can confirm that they were all correct.enigmaticcam wrote: ↑Tue Jul 31, 2018 11:44 pmI'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?
-
- Posts: 13
- 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 
