Primal Pi

[MerickOWA]

This is asking for the actual digits of pi? or just the number of digits? ... seems like a lot if its the actual digits.

[MerickOWA]

ok never mind i got it

[abc]

Is it right, that the answer has more than 1000 digits?

It is not asking for the number of digits - correct?

Greetings
abc

[MerickOWA]

Yep the answer is very very very long its not simply the number of digits

[abc]

Hi!

Question: Is there any page where I can found the primes between 1500 - 2048 Digits?
If your answer is yes - would you plz post the link?

(It spends about more than 30 minutes to test a prime with 1499 digits - so I think it will spend too much time to calculate all those longer primes...)

Thx
abc

[cyberwoozle]

I don't know, whether there's such a page on the internet, but even if you find one, i guess, pattern matching takes at least the same time as if you write a program for this challenge. The are pretty fast algorithms available to test big primes.
To reassure you: mine took around 8 hours

[MerickOWA]

Theres lots of pages that list the digits of pi, even out to one million decimal places. There probably isn't a page that shows that range and that range only.

http://www.joyofpi.com/pi.html (10,000 places)
http://www.geom.uiuc.edu/~huberty/math5 ... igits.html ( 100,000 places )
http://www.exploratorium.edu/pi/Pi10-6.html (1,000,000 places)

[snibril]

Take a look at OpenSSL, it helps.

[abc]

...I'm searching for primes - not pi...

[MerickOWA]

I don't think you'll find a website that lists primes that large. Once primes get that large, generating lists isn't generally helpful anymore. There are just too many. Its better to take numbers and try and determine if they're prime or not. Even if you found a website that listed primes that big, the number of possible primes they could list would be incredibly small compared to the number you'd have to search for in pi before you found a match.

[Chocoholic]

Take a look at OpenSSL, it helps.

Java can help here as well. My program ran around 24 hours till I got the right one though, and there may well be faster ways of doing the same.

@abc: I you are overlooking something there. If you have a look at the Prime-Counting Function [1] you will see that there are roughly 1,925,320,391,606,803,968,923 primes with only 23 digits or less. To list them all would take up roughly 19 Zettabytes (well, zebibytes to be precise). :)


[1] http://en.wikipedia.org/wiki/Prime-counting_function

[wodkahack0r]

Hm. I found a prime (size 1000 < x < 1200) but it doesn't seem to be the right one. But my program cannot find another prime, which has that much digits :-/

[Chocoholic]

Hm. I found a prime (size 1000 < x < 1200) but it doesn't seem to be the right one. But my program cannot find another prime, which has that much digits :-/

I suppose by "size 1000" you mean 1000 digits? Well, there are bigger ones.

[wodkahack0r]

Right. Well, then I need to adjust my script and try again.

[later]: Damn typo. Got it now.

[matter]

HINT: Every composite number can be written as the product of prime factors.

Sequence: consecutive digits in the first 2048 decimal places of pi

So, if you have a list of the first 100,000 prime numbers, you can 'test' each of the sequences, and whether one of those prime numbers is a factor of it. This way, you don't need to test 1, 2, 3, 4, 5, 6... instead you only test 2, 3, 5, 7...

I am using PHP with 68MB of memory to store a list of around 350,000 prime numbers. I recommend using at least that many primes.

Note: just because a number doesn't have any of these primes as a factor doesn't mean it is prime! You need to test up to the square root of a number to prove that it is prime (using this method). But it gives you sufficiently reduced number of sequences to test manually or for further factorisation.