10^999999+y (y=>1 to y<=5M) is sieved to p=2P with 80310 candidates remaining. The sieving is optimal for y~=2.7M :smile:

Sieving is currently paused and wont resume untill we gets near y=2.7M and will obviously never resume if a PRP is found for y<2.7M ... well let's see what the future holds.

Take care

Kenneth

[QUOTE=LaurV;301460][CODE]>> testrange(10^4999,10^4999+20000,10^8,20)
ans = 0
>>[/CODE]Yuck! Nothing, nada, niente. We expect one prime in 11 thousands numbers, at this score of 5k digits. It took about 20 minutes. Wasted. Try higher.
[/QUOTE]

This is a nit, but you don't need to use 20 MR witnesses per test at that size. 2 would give me a pretty good feeling about PRP-ness, and of course will run a lot faster. Also, since PRP tests take so long at that size, you are better off doing a lot more sieving to remove candidates.

[CODE]"testrange(10^4999,10^4999+20000,10^9,2)"[/CODE]
Took a couple minutes with 4 threads.

[QUOTE=bsquared;301481]This is a nit, but you don't need to use 20 MR witnesses per test at that size. 2 would give me a pretty good feeling about PRP-ness, and of course will run a lot faster. Also, since PRP tests take so long at that size, you are better off doing a lot more sieving to remove candidates.

[CODE]"testrange(10^4999,10^4999+20000,10^9,2)"[/CODE]
Took a couple minutes with 4 threads.[/QUOTE]

And what is the timing with 20 Rabin? Isn't the same? For most of the composites that survived sieve it takes only 1 Rabin Miller, and there was no prime in the interval.

[QUOTE=R. Gerbicz;301487]And what is the timing with 20 Rabin? Isn't the same? For most of the composites that survived sieve it takes only 1 Rabin Miller, and there was no prime in the interval.[/QUOTE]

Good point, I forgot it will stop after the first non-witness. I didn't time test this either but I think a little extra sieving would still be a win (10^9 vs. 10^8).

[QUOTE=bsquared;301481]This is a nit, but you don't need to use 20 MR witnesses per test at that size. 2 would give me a pretty good feeling about PRP-ness[/QUOTE]
Does it matter? If it came back empty handed, then all of them failed at the first (2-PRP) test. Of course the time depends on number of cores and CPU type/speed. I was using a single core of Core2Duo 2.8GHz. And of course there are much faster methods, but I only wanted to give some "starting points" for the people who believe that finding the smallest megaprime is easy.

edit: sorry, point discussed already (I read all the thread continuation after I replied to you). And yes, 10^9 could be a better trade, I also did not test all. As I just said, it is just a "starting point". If one could find "smallest PRP" with 5k, 10k, 50k (wow!) digits, then he could really appreciate what the people here are trying to do. When one say "finding a million digits prime", this looks easy, as we already know primes with 10 million digits.

edit2: yuck, did not see the thread was split...

The first three 5k digit PRPs.
10^4999+2*11335-1
10^4999+2*13606-1
10^4999+2*14717-1

2 minutes of newpgen to sieve to 5e9. 13 minutes on PFGW to test the whole range [On 1 core of 2GHz Core2 duo]

[QUOTE=KEP;291423]OK thanks, so to sum up:

Sieve depth is at p=1P (1 Peta) and continues to p=2P (2 Peta).

Thanks for teaching me something new :smile:

KEP![/QUOTE]

Do you even know what additional fraction of composites will be
removed when you raise the sieve bound from 10^15 to 2*10^15???

Do you know what the cost is of doubling the sieve bound here?

Are you aware that you should determine whether it is worthwhile?
(i.e. whether it will save time or cost additional time)
Do you know how to do that?

Hint: compute the cost of the additional sieving. compute how many
additional candidates it will remove. compute how long it would take
to run PRP tests if the sieve does NOT remove those candidates.

This task is COMPUTATIONALLY HOPELESS. As I already said, it
might be possible to find the smallest million digit PRP. Trying to prove it
prime is hopeless.

And although I have repeatedly told people to read the Pomerance & Kim
paper (regarding the probability that a PRP is actually a PSP), people
DO NOT GET THE MESSAGE.

It is clear that they do not get the message, because they would then
realize that [b]ONE[/b] PRP test is sufficient for numbers of this size.

This discussion of "multiple PRP tests" only goes to further my claim
that the people in this discussion DO NOT KNOW WHAT THEY ARE DOING.

Why don't you try READING about the state-of-the-art in prime proving
algorithms before continuing this ridiculous computation??????

The first three 15k digit PRPs:

10^14999+2*7496-1
10^14999+2*10991-1
10^14999+2*24125-1

I picked 15k because it's a size provable using PRIMO but I won't do so.

[QUOTE=R.D. Silverman;301520]This task is COMPUTATIONALLY HOPELESS. As I already said, it
might be possible to find the smallest million digit PRP. Trying to prove it
prime is hopeless.[/QUOTE]

I don't think anyone plans on proving it prime, just finding it.

[QUOTE=R.D. Silverman;301520]And although I have repeatedly told people to read the Pomerance & Kim
paper (regarding the probability that a PRP is actually a PSP), people
DO NOT GET THE MESSAGE.[/QUOTE]

I've read it (several times). Its Theorem 3.1 gives a weak upper bound here of about 4.4 * 10^-1254 on the chance that a random pseudoprime of this size would be composite. A better bound could be produced by (approximately) solving the optimization problem in Theorem 4.4. But in any case it's quite unlikely that a random PrP this large is composite.

For those who haven't read the paper: this cannot simply be powered like the Monier and Rabin 1/4 result on strong pseudoprimes: if a composite passes one test it's dramatically more likely to pass a second test than a random composite.

[QUOTE=R.D. Silverman;301520]Do you even know what additional fraction of composites will be
removed when you raise the sieve bound from 10^15 to 2*10^15?[/QUOTE]

About 1 - log(1e15)/log(2e15) ≈ 2% of the number remaining, saving about 1311 prp tests on average. The standard rule of thumb says it's worthwhile if the additional sieving takes less than 1311 times the cost of a single test. If the plan is to test a few numbers and then give up if it's not found easily, that makes additional sieving less valuable.

[QUOTE=R.D. Silverman;301520]
This discussion of "multiple PRP tests" only goes to further my claim
that the people in this discussion DO NOT KNOW WHAT THEY ARE DOING.
[/QUOTE]
Who was talking about multiple PRP tests for a mega-number? Point the guy. Or if not, tell us why we won't do multiple PRP tests for a 5k-digitd-number...:razz: