Primes in π

[davar55]

Originally Posted by CRGreathouse

He since increased it to 127,523 if I read this correctly:
http://mathworld.wolfram.com/IntegerSequencePrimes.html

That appears to be the latest search limit, not itself prime; if I read that
list correctly. So a(96) is longer (yay). News on a(20)?

[Batalov]

No, ran some more than rebooted ...and into the bit bucket the trail went.

I was going to refactor (probably with a "real" sieve) and then rerun a(20) in another base from the start. The previous perl sieve was a toy:

for($j=1;$j<$l-$i;$j++) {
  $d=substr($_,$i+$j,1);
  $s=(10*$s+$d) % 999999;
  print substr($_,$i,$j+1),"\n" if($d =~ /[1379]/ && gcd($s, 999999)==1);
                                #this takes care of 2,3,5,7,11,13,37
}

[davar55]

Originally Posted by Batalov

No, ran some more than rebooted ...and into the bit bucket the trail went.

I was going to refactor (probably with a "real" sieve) and then rerun a(20) in another base from the start. The previous perl sieve was a toy:

for($j=1;$j<$l-$i;$j++) {
  $d=substr($_,$i+$j,1);
  $s=(10*$s+$d) % 999999;
  print substr($_,$i,$j+1),"\n" if($d =~ /[1379]/ && gcd($s, 999999)==1);
                                #this takes care of 2,3,5,7,11,13,37
}

Are all these perl variables automatically strings?
W/O any declarations, and not yet having used perl,
I wasn't sure. Looks like they're pre-initialized - to null?
(I'm referring particularly to $l and $i in the for loop control,
but they can't both be null - oh well).
I see it's basically C. I'll have to look up perl.

[Batalov]

This is just a replacement shippet of the full code (which was posted earlier), where $p is a long string with 250000 digits of following "20" ($i is the offset of "20"). I've attached here the latest variation, that saves on disk space and spawns pfgw on chunks.

Originally Posted by Batalov

Well, ok, records are made to be broken. With a bit of luck I found a 140,165-digit PRP that starts with the first "96" in Pi, the a(96). a(20) is still ongoing.

EDIT2: strictly speaking, because a(96) is quite big - it may not be a minimal solution: ...

a(96) is double-checked (this time using base 2) and is the minimal solution. The gaps, if there were any, are now covered.

a(20)>10^215000. I've stopped the search.

[davar55]

Does anyone think this series is oeis-worthy?
As OP I'm not entitled to an opinion.
But some of those PRPs batalov discovered
are eye-worthy, I think.
Maybe when a(20) is finally tackled ...

[davar55]

a(96) is double-checked (this time using base 2) and is the minimal solution. The gaps, if there were any, are now covered.

a(20)>10^215000. I've stopped the search.

Any news? Have you run it further?

What would it take to PRP test an unknown (C or P)215000?

Can you tell us the first 200 digits in pi of a(20)?

[kar_bon]

Generate your Pi with y-cruncher.

[davar55]

Wouldn't want to crunch too many y''s, they're rare enough.

I see the first 20 occurs at digit 53.

Thanks.

[danaj]

I decided to give this a go, since it lends itself well to Perl, and seemed like a useful test case for my module. Attached is a simple serial script that outputs the result (using the "skip uninteresting" criteria) with a BPSW test all done in Perl, and no need for presieving etc. Thanks to Batalov for the initial script.

I've gone through all the numbers to 100 other than a(20) which I've got to 231k. All results pass BPSW, M-R with bases 3 and 5, and the Frobenius-Underwood test. I also had it run a proof (BLS75 theorem 5 or ECPP) on anything under 1000 digits. All of this is easily available in Perl. I used the "skip uninteresting numbers" variant, and I start with the first occurrence of the target number, so a(10) = PRP(19128), a(12) = PRP(211).

I also wrote a threads version where multiple threads pull lengths off a shared queue. I ran it for a(20) for a while on 48 cores of a Power7 machine. Starting at 214000 it got to 231000 before I had to quit. I'll run it with 12 threads on my Intel machine next. It's ugly managing the locks, writing out checkpoint marks, and making sure we output the minimum digits found rather than the first one found. I can post a link if anyone wants it.

To get the 'Pi-2M.txt' file I used y-cruncher, but at only 2M digits there are plenty of other tools that would do it.

The more interesting numbers, with their PRP digits:
10 -> 19128
17 -> 6918
20 -> ??? >231000
62 -> 3490
80 -> 41938
81 -> 4834
84 -> 3057
96 -> 140165
97 -> 821
98 -> 61303

[Digressions ahead]

This is convenient, but is it fast? The BPSW test is faster than Pari, and the next_prime function is much faster than PFGW 3.7.7 for 2000+ digit inputs (digressing even more here, but perhaps PFGW isn't doing any sieving of candidates, or perhaps I'm using it wrong. "say next_prime(2**6600)-2**6600" takes ~30s for my code, "nextprime(2^6600)-2^6600" takes a bit under 2 minutes for Pari 2.6.1, while "./pfgw64s -V -q'nextprime(2^6600)'" takes over 4 minutes). However, PFGW's PRP tests are definitely faster (3.7.7 AVX FFT).

Well, everything is looking fine until we get into 30k+ digits. PFGW is much faster there (I imagine those familiar with it are eminently unsurprised). There isn't much I can do about the PRP tests, but it did give me the push I needed to put in a rudimentary treesieve (thanks to Jens Andersen for the nice writeup), which speeds up my trial division step for big numbers. Probably the fastest complete solution would be to put in a function like is_smooth($n, $B) that would just do the initial trial division, then we let PFGW handle the PRP tests on what's left.

To give some idea of just how bad this gets, for a(96), a 140,165 digit PRP on my computer:

5m 50s PFGW (Fermat)
6m 15s PFGW (F-strong)
26m 30s PFGW (Fermat and Lucas PRP)
30m 15s MPU::GMP is_strong_pseudoprime($n,2) (1 M-R)
63m 40s Pari 2.6.1 ispseudoprime($n,1) (1 M-R)
85m 45s MPU::GMP ES Lucas test
90m 15s MPU::GMP Frobenius-Underwood test
115m 55s MPU::GMP is_prob_prime (ES BPSW)
127m 0s MPU::GMP strong Lucas test
206m 20s mpz_prp is_strongbpsw_prime (S BPSW)
213m 15s Pari 2.6.2 ispseudoprime($n) (AES BPSW)

It's much closer at 10k digits. Also until we hit the PRP at this range basically everything would be found composite by the SPSP-2 test, so we just pay the cost of the SPSP test until we found the prime where we do the full BPSW cost. The result has also passed BPSW when we're done, which we probably would have wanted to do anyway.

[J F]

Hi!

I did read this (then long dead) thread in early summer
and played around. Now some activity again, maybe
someone is interested in some newer numbers.
It seems me setting the end point to 1111 was
a bit optimistic...

[danaj]

JF, very impressive. What did you use for the primality testing?

I noticed you're not including the initial 3 in your search (e.g. you have 314 starting at 2120 instead of 0). I guess it's a bit ambiguous, but I read "digits of Pi" rather than "decimal digits of Pi".

I suspect dropping the "uninteresting" restriction I used (where we don't allow the result to be equal to the number) is probably best if the series is extended far enough.

There are a couple typos in the results:
- number 119 the start is at 494, not 404
- number 471 the length is 8610, not 8619

With corrections above, all results from your list with length < 100,000 verified with BPSW.