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


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
Post Reply
hvdboorn
Posts: 5
Joined: Fri Apr 27, 2012 1:01 am

Problem 381

Post by hvdboorn » Fri Apr 27, 2012 3: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!
Image

hvdboorn
Posts: 5
Joined: Fri Apr 27, 2012 1:01 am

Re: Problem 381

Post by hvdboorn » Fri Apr 27, 2012 5: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
Image

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

Re: Problem 381

Post by ralu » Thu May 03, 2012 11:15 pm

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.

User avatar
jaap
Posts: 514
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Problem 381

Post by jaap » Fri May 04, 2012 12:10 am

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

Post by ralu » Fri May 04, 2012 12:21 am

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

Post by TripleM » Fri May 04, 2012 1:01 am

Try the 3rd word of the problem statement :)

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

Re: Problem 381

Post by ralu » Fri May 04, 2012 1:03 am

How dumb i was.

Thanx

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

Re: Problem 381

Post by enigmaticcam » 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?

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

User avatar
RobertStanforth
Administrator
Posts: 544
Joined: Mon Dec 30, 2013 11:25 pm

Re: Problem 381

Post by RobertStanforth » Wed Aug 01, 2018 7:12 am

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: 7
Joined: Tue Sep 29, 2015 11:07 pm

Re: Problem 381

Post by enigmaticcam » Wed Aug 01, 2018 5:10 pm

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

Post Reply