Problem 007

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.
User avatar
hk
Administrator
Posts: 9873
Joined: Sun Mar 26, 2006 9:34 am
Location: Haren, Netherlands

Re: Problem 007

Post by hk » Wed Jul 20, 2011 2:02 pm

We've heard that before.
More often than not it turns out that people found the 1001st prime, while the 10001st prime is asked for.
Image

coziroyc
Posts: 2
Joined: Wed Jul 20, 2011 1:36 pm

Re: Problem 007

Post by coziroyc » Wed Jul 20, 2011 9:29 pm

You're right. I found the 1001st prime. I thought I read the instructions carefully. Oops.

machine_easy2
Posts: 11
Joined: Tue Jul 12, 2011 6:23 am

Re: Problem 007

Post by machine_easy2 » Sat Sep 17, 2011 5:22 pm

I keep getting a few numbers passing through my sieve that are not prime. In my list of "the first 30 primes" I'm getting an incorrect 27 and 95....

Any help??

machine_easy2
Posts: 11
Joined: Tue Jul 12, 2011 6:23 am

Re: Problem 007

Post by machine_easy2 » Wed Sep 21, 2011 8:35 am

machine_easy2 wrote:I keep getting a few numbers passing through my sieve that are not prime. In my list of "the first 30 primes" I'm getting an incorrect 27 and 95....

Any help??
Better loop control.

mavritivs
Posts: 4
Joined: Fri Jun 01, 2012 3:03 am

Re: Problem 007

Post by mavritivs » Mon Jun 11, 2012 4:37 am

I am using Fermat's Little Theorem for this, but I am getting an error. For prime #69, it lists "341". I double checked this with another script of mine to check for primality. It says 341 is not prime. Could anyone tell me what I am doing wrong or look at my code for mistakes? I really cannot seem to find one.

Thanks.
Image

mdean
Posts: 140
Joined: Tue Aug 02, 2011 1:05 am

Re: Problem 007

Post by mdean » Mon Jun 11, 2012 7:26 am

You probably shouldn't be posting how you attempt to solve the problem. I have a feeling you might find this relevant though: http://en.wikipedia.org/wiki/Fermat%27s ... eudoprimes
Image

mavritivs
Posts: 4
Joined: Fri Jun 01, 2012 3:03 am

Re: Problem 007

Post by mavritivs » Mon Jun 11, 2012 4:14 pm

I only mention Fermat since it was already mentioned in the beginning of this thread.
Thanks a lot for that link, I do not know how I overlooked that section on wikipedia.
Image

thundre
Posts: 356
Joined: Sun Mar 27, 2011 9:01 am

Re: Problem 007

Post by thundre » Mon Jun 11, 2012 6:55 pm

mavritivs wrote:I am using Fermat's Little Theorem for this, but I am getting an error. For prime #69, it lists "341". I double checked this with another script of mine to check for primality. It says 341 is not prime. Could anyone tell me what I am doing wrong or look at my code for mistakes? I really cannot seem to find one.
Fermat's Little Theorem is more useful for proving which numbers are composite than which are prime. It can be used as a first check, so you can avoid the more time-consuming full check in most cases.

See http://en.wikipedia.org/wiki/Carmichael_number

341 = 11 * 31, so it is composite.

2 and all powers thereof are Fermat liars in base 341. But 3^341 % 341 = 168.
Image

pcworx
Posts: 6
Joined: Wed Nov 27, 2013 3:52 pm

Re: Problem 007

Post by pcworx » Wed Jan 01, 2014 9:44 am

Man I hope this isn't giving away too much on the solution, but seeing how there are several prime number problems I just wanted to verify one thing. Once your divisor is 1/2 of the potentialprime number there isn't any reason to keep dividing right? I mean let's say 101 is a prime, once your divisor test is up to 51 there is no point in going on up higher with your divisor because the result will be less than 2? I am new to math and programming so forgive me if I have done wrong....just a dumb American here.

User avatar
nicolas.patrois
Posts: 117
Joined: Fri Jul 26, 2013 3:54 pm
Contact:

Re: Problem 007

Post by nicolas.patrois » Wed Jan 01, 2014 10:48 am

Beware, 341 is not a Carmichael number. Carmichael numbers are pseudo primes in any prime base.
The first Carmichael number is 561.
Image

LarryBlake
Posts: 97
Joined: Sat Aug 29, 2009 7:49 pm

Re: Problem 007

Post by LarryBlake » Wed Jan 01, 2014 3:30 pm

pcworx, you're right that you don't need to test above half the number. You can actually stop testing sooner than that if you think about it a little further.
Image

Post Reply