Primes in π
Finding primes in the digits of pi has been done,
so here is yet another primes in pi puzzle. For every positive integer n (in decimal) find the first occurrence in pi of the digits of that integer, then the first prime constructed from the subsequent digits of pi. Here's what I had in mind: __________________________________ 1 > 14159 2 > 2 [STRIKE]26535897932384626433[/STRIKE] (*) 3 > 3 4 > 41 5 > 59 (*) 6 > 653 7 > 79 (*) 8 > 89 9 > 9265358[COLOR=sienna]97[/COLOR]9323 [COLOR=darkred](or 97 ??)[/COLOR] 10 > [COLOR=#8b0000]102701 [COLOR=black](or[/COLOR] [/COLOR][COLOR=darkred]1058209749...6531873029[/COLOR][SUB]<19128>[/SUB] ?) (PRP) 11 > 11 12 > 12847564823 (or[COLOR=#8b0000] 12848111...678925903[/COLOR][SUB]<211>[/SUB] ?) ... [COLOR=green]20 > [COLOR=darkred](...more than 215000digit...)[/COLOR][/COLOR] [COLOR=green][COLOR=darkred]...[/COLOR] 62 > 3490digit Prime (and three more PRPs) 80 > 41938digit PRP. 81 > 4834digit PRP. 84 > 3057digit PRP. 96 > [B][COLOR=darkred]140165digit PRP[/COLOR][/B]. 98 > 61303digit PRP.[/COLOR] [COLOR=black]up to 100 (except 20): all primes/PRPs are less than 1000digits or shown above[/COLOR] __________________________________ (*) of course 2, 5 and 7 are prime (**) My calculator only checks for small factors, so * and ** may not actually be prime I think the list carried to (at least) 100 will possibly contain some more interestingly large primes, or will the primechecking facility be tested only by going to 1000, or beyond? _______________ [COLOR=darkred]P.S. I could restore the original values for 2 and 10, but ... they were composite. You can easily see the original in post #2 (SB)[/COLOR] 
[QUOTE=davar55;304822]Finding primes in the digits of pi has been done,
so here is yet another primes in pi puzzle. For every positive integer n (in decimal) find the first occurrence in pi of the digits of that integer, then the first prime constructed from the subsequent digits of pi. Here's what I had in mind: 1 > 14159 2 > 26535897932384626433 (*) 3 > 3 4 > 41 5 > 59 (*) 6 > 653 7 > 79 (*) 8 > 89 9 > 9265358979323 10 > 1058209749445923078164062862089986280348253421170679821480865132823 (**) 11 > 11 12 > 12847564823 (*) of course 2, 5 and 7 are prime (**) My calculator only checks for small factors, so * and ** may not actually be prime I think the list carried to (at least) 100 will possibly contain some more interestingly large primes, or will the primechecking facility be tested only by going to 1000, or beyond?[/QUOTE]Another, related problem, would be to to find the first radixn representation of primes in the radixn representation of \pi which begin with the digit n1 for all integer n >=2. Alternatively, those primes which begin with each of the digits <n in the radixn representation of the primes and of \pi Paul 
26535897932384626433 = 150917801 x 175830139033
1058209749445923078164062862089986280348253421170679821480865132823 = 196699 x 1834313671 x 4817619413830406641955201 x 608784400187359263779612387 
For 12, the value appears to be
[CODE]1284811174502841027019385211055596446229489549303819644288109756659334461284756482337867831652712019091456485669234603486104543266482133936072602491412737245870066063155881748815209209628292540917153643678925903[/CODE] But for 10, ...that's a real beauty! Makes one wonder that the first possible chain of digits might go without a prime (can it? on a simple probabilistic argument?), then the next one easily produces [SPOILER]102701[/SPOILER] (*** same below) 13 > 13 14 > 14159 15 > 1592653 16 > 1693 17 > 17 18 > 1861 19 > 19 20 > 20................................... or 2089 (***) 21 > 211 22 > 223 
There shouldn't be a probabilistic argument, really. (Silly me.)
On one hand, these candidates are not sparser than any quasi/nearrepunits (one per a power of 10  except for some series with algebraic compositeness),  and we have tons of primes/PRPs for them. On the other hand, I actually found the 19128digit PRP (easy to recontruct from Pi, code is below; decimal view: 1058209749...6531873029). Now we need a healthy volunteer to prove it; it would be a Primo record! [CODE]# gp \p 20000 write("p10",floor(Pi*10^19176)%(10^19128)) \q pfgw f tc p10 [/CODE] I still don't have a PRP for 20.............. though. 
I appreciate the editing of my OP.
It was after all just a starting point. For the sake of completeness, since 10..... and 20..... are producing long sequences, it might be interesting to check 30....., 40....., etc. 
I hoped that you wouldn't mind. Thank you for a nice problem!
30 and 40 turned out to be easy. 20 is still running empty (at least 9300 digits in it). In the meantime, I installed a shiny new Bosch dishwasher to please SWMBO. "Change of work is rest", they say? :) EDIT: ...oh and for 2, I found a 50digit prime, but then again, the mere "2" is already prime. 
You're aware that the first primeinstance might not necessarily start at the first instance?
(this is the same mistake as Shallit made) J 
1 Attachment(s)
The following pari code finds solutions for 2 digit starting points upto length 1000.
[CODE]\p 20000 { found=0; for (n=10, 99, for (offset=0, 1000, if ((floor(Pi*10^(2+offset1))%(10^2))==n, for (digits=2, 1000, f=factor(floor(Pi*10^(digits+offset1))%(10^digits),9); if (matsize(f)==[1,2], if (ispseudoprime(floor(Pi*10^(digits+offset1))%(10^digits),20), print(floor(Pi*10^(digits+offset1))%(10^digits)); found=1; break; ); ); ); if (found==0, print("A solution has not been found for " n); ); found=0; break; ); ); ); } \q [/CODE] I have attached solutions for 1099 that I have found. The following have no solutions upto 1000. [CODE]10 20 62 80 81 84 96 98[/CODE] All this is ignoring what bearnol just pointed out. I will now write a script that produces input to pfgw for the harder numbers. Is there a way of redirecting the output from a pari script without getting things like the header as well? I am a bit of a pari novice. 
[QUOTE=henryzz;304913]Is there a way of redirecting the output from a pari script without getting things like the header as well? I am a bit of a pari novice.[/QUOTE]Yes.
Here's how the Perl script which is used to update my factor table tests its argument for primality. [code] # Primality testing function. # Initial sanity check to see whether Pari/gp is installed and working correctly. my $sc1 = `echo "isprime(1074884750872101952308847649628260864479,2)"  /usr/bin/gp f q`; # Known prime. my $sc2 = `echo "isprime(1074884750872101952308847649628260864481,2)"  /usr/bin/gp f q`; # Known composite. ($sc1 != 1 or $sc2 != 0) and die "Failed gp sanity check\n"; sub is_prime($) { my $num = shift; my $big_mem = length $num > 300 ? 'allocatemem(104857600);' : ''; return `echo "${big_mem}isprime($num,2)"  /usr/bin/gp f q ` == 1; } [/code] You should be able to read Perl well enough to translate that function into the language of your choice. Paul Paul 
[QUOTE=bearnol;304883]You're aware that the first primeinstance might not necessarily start at the first instance?
(this is the same mistake as Shallit made) J[/QUOTE] Would you care to expand on this? How would you move on from the first instance to the next one? By proof? For example could you prove that there can not be a prime in these series: 1) 7019*10^n1 or in 2) 8579*10^n1. (subsequences of pi would be obviously harder) [SPOILER]Yes, 2) is a trick proposition. There exists a prime.[/SPOILER] 
For 62, the PRP is 3490digit.
For 81, the PRP is 4834digit. For 84, the PRP is 3057digit. (these would be easy to prove prime) 
[QUOTE=Batalov;304950]For 62, the PRP is 3490digit.
For 81, the PRP is 4834digit. For 84, the PRP is 3057digit. (these would be easy to prove prime)[/QUOTE] How far are you testing? 
I have 50000 Pi digits dumped from gp and then prefiltered by a simple perl script that takes care of small factors of 2,5 (easy!) and 3 (simple sum of digits). 7 and 11 could be easily added but is not of significant help.
Then the candidate file goes to pfgw f. All very easy, very 'umble. For 20, 80, 96 and 98, the PRPs would be larger than 30,000 digits now. 
[QUOTE=Batalov;304937]Would you care to expand on this?
How would you move on from the first instance to the next one? By proof?[/QUOTE] By using a notcompletelyinsane method. In the outer loop, you take the first N digits of pi; in the inner loop, you take the last M digits of those N digits and test if that number begins with the specified digit(s) and is prime. Optimizations are possible: the outer loop can skip those N where the last digit is even, and the inner loop can keep a table of the positions of the starting digit(s). 
That's not what I meant. The inner loop is already done to death. You simply cannot use the outer loop (as the problem is stated).
Suppose we are searching for a(20). [CODE]pi = 3. 14159265358979323846264338327950288419716939937510 58[COLOR=darkred][B]20[/B]974944592307[/COLOR]816406286[COLOR=blue][B]20[/B]8998628034[/COLOR]8253421170679 82148086513282306647093844609550582231725359408128 48111745028410270193852110555964462294895493038196... [/CODE] Suppose we've checked the substrings starting from the red [COLOR=darkred][B]20[/B][/COLOR] up to a length of million and didn't find a prime. That doesn't give us the right to move on to the blue [COLOR=blue][B]20[/B][/COLOR], find [COLOR=blue][B]20[/B]89[/COLOR] and say that we are done. We can only move on to the next instance of the starting point [I]after[/I] we have proven that there are no primes formed by the first instance. Can we prove that? 
Do you (the general "you") define the "first prime instance" using the starting position or the ending position?
Explicit clarification is called for. 
The problem is stated somewhat loosely and is open to interpretations.
Clearly we can all agree that the first, say, '3' after the prefix is not what OP intended. (Even though he wrote, "the first prime constructed from the subsequent digits".) But I can see how you can interpret that as the string becomes longer it absorbes more instances of the prefix and you can hop onto that prefix. I think that this variant is too easy. It probably can be solved up to 56digit values. Too easy. Indeed, I am interested in the hard variant (For a given number [I]n[/I], find the leftmost instance of a prime substring in decimal expansion of pi that starts with [I]n[/I].) It can still be not the first useable prefix. P.S. For the easy interpretation, 1 > 41, isn't it? Maybe not (that's yet another interpretation). But surely, for the easy interpretation, 9 > 97 
[QUOTE=Batalov;305006]T
We can only move on to the next instance of the starting point [I]after[/I] we have proven that there are no primes formed by the first instance. Can we prove that?[/QUOTE] IANANT, but the infinite sum of 1/ln(n) diverges, so even accounting for the fact that on average we only sum 4 of every 10 terms, I would think that the probability that there exists a prime would be 1. edit: here is where it would be nice for RDS to come around, slap me upside the head, and give a correct answer. I just put my $0.02 worth of thought into it. 
80 > 8034825342...6216977871[SUB]<41938>[/SUB]
Formula: floor(Pi*10^42021)%(10^41938). (Submitted to Lifchitz&Lifchitz...) edit: I just put my $0.25 in the swear jar. B> 
Indeed, the problem being solved by Batalov and henryzz et.al.
is the one I intended in the OP. Only if no prime exists in pi at a found point should the next occurrence of the integer be used. I see why this wasn't all clear in the OP. 
I Am Not A National Treasure???

[QUOTE=Dubslow;305072]I Am Not A National Treasure???[/QUOTE]
Clearly not :) but also not a Number Theorist. 
98 > 9862803482...07182848167[SUB]<61303>[/SUB] PRP

[QUOTE=Batalov;304950]For 62, the PRP is 3490digit.
(...) (these would be easy to prove prime)[/QUOTE] ... is proven prime [url=http://factordb.com/index.php?id=1100000000524129946]here[/url]. 
a(20) and a(96) both would be larger than 71000 digits. Running up to 100k digits.

1 Attachment(s)
Here's some code for finding possible numbers of PIdigitprimes for testing with pfgw.
All needed info. are given in the attachment. 
Ah. Interesting to compare different programming styles.
Here's my scriptus. [CODE]#!/usr/bin/perl w $N=(shift  '20'); # Pi is prepared by gp :: \p 100000; write("Pi",Pi) open IN, "Pi"; $_=<IN>; s/\s+$//; $l=length($_); for($i=0;$i<length($_) && (substr($_,$i,length($N)) ne $N);$i++) {} die unless substr($_,$i,length($N)) eq $N; $s3=substr($_,$i,1); # sum of digits for divisibiltyby3 test for($j=1;$j<$l$i;$j++) { $s3+=substr($_,$i+$j,1); print substr($_,$i,$j+1),"\n" if(substr($_,$i+$j,1) =~ /[1379]/ && $s3%3!=0); } #then run pfgw f cfile [/CODE] 
IMHO, it makes some of the sequences "uninteresting" if we allow the number itself as a prime. To make them more interesting, I think that only primes with digits added should be allowed. Doing this, we have the following smallest primes from the 1st post of this thread:
[code] 1 > 14159 2 > 26535897932384626433832795028841971693993751058209 3 > 31 4 > 41 5 > 59 6 > 653 7 > 79 8 > 89 9 > 9265358979323 10 > (41938digit PRP already posted) 11 > 1170679 12 > 1284811174502841027019385211055596446229489549303819644288109756659334461284756482337867831652712019091456485669234603486104543266482133936072602491412737245870066063155881748815209209628292540917153643678925903 [/code] Using the restriction of disallowing the number (sequence) itself as a prime, does this affect any already calculated results for sequences > 12 ? 
[QUOTE=gd_barnes;305563]Using the restriction of disallowing the number (sequence) itself as a prime, does this affect any results for sequences > 12 ?[/QUOTE]
13, 17, 19, 23, 29,... and many others (see file in post #9). 
[QUOTE=kar_bon;305565]13, 17, 19, 23, 29,... and many others (see file in post #9).[/QUOTE]
Ah very good. Based on that, I would pose it as an additional difficulty to the problem to find primes with digits added to the 2digit prime sequences. 
17 gets in a spot of trouble [SPOILER]but it has a 6918digit PRP[/SPOILER]. Others (I checked only a few ...up to 100... 200) escape easily.

Based on the OP looking for certain primes among the digits of pi,
where is the first occurrence of each successive prime in pi, i.e. the first "2", ... , the first "97", etc. up to say 100000. Indexing could begin with the 3 as 1 or 0. There are repetitions and the sequence is not in numerical order. (I have not computed this sequence.) Also, where are the first occurrences of the Mersenne prime exponents. (The 8 digit ones may be far to find.) 
[QUOTE=davar55;307534]Also, where are the first occurrences of the Mersenne prime exponents.
(The 8 digit ones may be far to find.)[/QUOTE] Searched the first 1,000,000,000 digits of PI to find this (leading '3' not counted): [code] Mers Expo start in PI at digit 2 6 3 9 5 4 7 13 13 110 17 95 19 37 31 137 61 219 89 11 107 1487 127 297 521 172 607 286 1279 11307 2203 1910 2281 19456 3217 959 4253 7337 4423 7591 9689 690 9941 1073 11213 47802 19937 115211 21701 28507 23209 280538 44497 85342 86243 89373 110503 808004 132049 840293 216091 3226144 756839 996061 859433 2887812 1257787 24078017 1398269 2037623 2976221 20104152 3021377 1220576 6972593 9252419 13466917 39603620 20996011 40909479 24036583 8854005 25964951 19456503 30402457 645842094 32582657 510029176 37156667 53909580 42643801 228338527 43112609 248103197 [/code] Curious: Mersenne expo 127 starts at index 297 which is 129[sub]16[/sub]. 
What is the largest known prime in the sequence of digits of pi?

[QUOTE=Xyzzy;307574]What is the largest known prime in the sequence of digits of pi?[/QUOTE]
[url]http://oeis.org/A060421[/url] supposedly shows that one known one is up to over 78000 digits depending on how you define a [URL="http://mathworld.wolfram.com/PiPrime.html"]pi prime[/URL] 
[QUOTE=science_man_88;307603][URL]http://oeis.org/A060421[/URL] supposedly shows that one known one is up to over 78000 digits depending on how you define a [URL="http://mathworld.wolfram.com/PiPrime.html"]pi prime[/URL][/QUOTE]
It said 78073. I think it's remarkable that batalov's computations are going to or have already exceeded that. 
I've halfheartedly tried to check the same run up from 78073 to 100k (and the a(20) and a(96) to 100k)  no primes (and then the run gets slow), so prp78073 holds the palm d'or as far as we know. It can be easily beaten with random starts and in the range of lengths from 78074 to 8085k, but that would be fairly pointless  that in turn would be easily beaten.

[QUOTE=Batalov;307923]I've halfheartedly tried to check the same run up from 78073 to 100k (and the a(20) and a(96) to 100k)  no primes (and then the run gets slow), so prp78073 holds the palm d'or as far as we know. It can be easily beaten with random starts and in the range of lengths from 78074 to 8085k, but that would be fairly pointless  that in turn would be easily beaten.[/QUOTE]
The OP did suggest the sequence from 1 to 100 ... (Don't want to light any fires, but breaking records is always fun.) 
[QUOTE=Batalov;307923]I've halfheartedly tried to check the same run up from 78073 to 100k (and the a(20) and a(96) to 100k)  no primes (and then the run gets slow), so prp78073 holds the palm d'or as far as we know. It can be easily beaten with random starts and in the range of lengths from 78074 to 8085k, but that would be fairly pointless  that in turn would be easily beaten.[/QUOTE]
How about "Our sequence can beat your sequence" as a humorous motivation? I would love to know the length of the values for 20 amd 96. 
They are longer than 103,000 digits. :)

[QUOTE=Batalov;308151]They are longer than 103,000 digits. :)[/QUOTE]
Love that emoticon. I do believe there's something up your sleeve ..... 
Because pi has an infinite number of digits, it's almost certain that every possible sequence can be found. I wonder how far one will have to go in order to find, say, M#47?

a(96) = 140,165digit PRP
Well, ok, records are made to be broken. With a bit of luck I found a 140,165digit PRP that starts with the first "96" in Pi, the a(96). This may also be the largest known PRP in the sequence of digits of Pi, for Xyzzy.
I [strike]am DCing[/strike] have doublechecked it in a few bases and with combined N+1/N1 and submitted to Lifchitz. Here's the code to generate the number for the independent checks: [code]# Pari/GP # \p 143000 prp=floor(Pi*10^140344)%10^140165; # passes the GP ispseudoprime(prp) test, too, in addition to PFGWbased PRP and BLS [/code] a(20) is still ongoing. EDIT2: strictly speaking, because a(96) is quite big  it [I]may[/I] not be a minimal solution: there's a chance that by way of some bug I [I]could[/I] have missed some smaller PRP (I also have a small gap between two threads that processed candidates above and below 125,000 digits, which I will close sometime soon; I may rerun the whole search using a different base for PRP, too  or anyone else is welcome to. The scripts are all here, in this thread.) 
Using a bit different logic I confirm all the PRP values with <200 digits found up to now. Moreover, if we let apart the leading "3" and use only the digits in the fractional decimal expansion, that would modify the primes for 3 and 31:
[CODE] (11:46:26) gp > get_primes_in_pi(0,100,1,1) Found 0 at position 32. Checking for prime ... Found: prp=2 Found 1 at position 1. Checking for prime ... Found: prp=14159 Found 2 at position 6. Checking for prime ... Found: prp=26535897932384626433832795028841971693993751058209 [COLOR=Red]Found 3 at position 9. Checking for prime ... Found: prp=35897[/COLOR] Found 4 at position 2. Checking for prime ... Found: prp=41 Found 5 at position 4. Checking for prime ... Found: prp=59 Found 6 at position 7. Checking for prime ... Found: prp=653 Found 7 at position 13. Checking for prime ... Found: prp=79 Found 8 at position 11. Checking for prime ... Found: prp=89 Found 9 at position 5. Checking for prime ... Found: prp=9265358979323[/CODE] [CODE]Found 30 at position 64. Checking for prime ... Found: prp=307 [COLOR=Red]Found 31 at position 137. Checking for prime ... Found: prp=317 [/COLOR]Found 32 at position 15. Checking for prime ... Found: prp=32384626433832795028841971693993751058209749445923078164062862089986280348253421 Found 33 at position 24. Checking for prime ... Found: prp=33832795028841971 Found 34 at position 86. Checking for prime ... Found: prp=348253 Found 35 at position 9. Checking for prime ... Found: prp=35897 Found 36 at position 285. Checking for prime ... Found: prp=3607[/CODE] The last parameter is "only_non_trivial_primes" that is, extend the numbers if they are prime already, and the third parameter is "use only decimal expansion (ignore the leading 3)". 
For the leading zero, the following prime must be in octal*! :)
(this doesn't change the answer though, it's still "02") Also, I've revisited the larger PRPs and let the searches run for a while more and found a few more PRPs starting with the leftmost "62": 3490, 7734, 11111, and 17155digit (the last two are reportable to Lifchitz[SUP]2[/SUP]) ______ *C convention. printf("%d\n", 052); will print 42 
[QUOTE=Batalov;308875]For the leading zero, the following prime must be in octal! :)
[/QUOTE] :razz: Joking apart, I just did a recheck for all thingies under 10k digits. With this occasion I found out that everybody completely missed 97. It was prime by itself in the "trivial" case, so it was not mentioned in post #9, and it was forgotten after the rules changed. My pari found a [URL="http://factordb.com/index.php?id=1100000000530494297"]nice 821 digits[/URL] beauty for it starting from position 12. 
It was not forgotten in post #32. PRPs under 1000 digits are too easy to even mention. (And Lifchitz site has a cutoff of 10000 digits.)
Only 17 was slightly more challenging. 
Ah, ok then.
I anyhow reported to FDB the PRPs for 54 and 73 (with 499 respective 446 digits) which were not reported, after I rediscovered them, together with the PRP for 97 in discussion. 
Were you doing a(20) and a(96) in parallel?
So is length of a(20) already known > length of a(96), assuming it resolves finitely? Great work. 
You can look in another way : Is the first N digit of pi (including 3)is a prime ?
Have a look at this 3 31 314159 31415926535897932384626433832795028841 what is the next "PIPRIME"? ps I'm poor in English ..... sorry 
Yes, this is the sequence [URL="http://oeis.org/A005042"]A005042[/URL]
(the extended version of the [URL="http://oeis.org/A060421"]A060421[/URL] sequence). We've already discussed these above. I suspect that multiple people searched for larger members of this sequence (in other words, we shouldn't think that the search stopped at the 78073; E.W.W.'s [URL="http://mathworld.wolfram.com/PiPrime.html"]mention[/URL] of the upper search limit is 6 years old). 
The OP defined a single sequence, but somewhat loosely.
There are really an infinite number of sequences f[sub]i[/sub] with the OP defining f[sub]1[/sub]. In that sequence, though it wasn't perfectly clear due to the calculations presented, the primes were intended to be represented by themselves (e.g. a(2) = 2 not the P50 that was found ). But the examples showed that the OPer was uncertain about that point. So f[sub]2[/sub] would be the sequence of primes starting at all the same places in pi but the SECOND prime found. Similarly for f[sub]3[/sub] and up. I think just the first two sequences would cover all that the OP intended, but finding the primes starting at ANY point in pi (as e.g. from the 3 prefix, which is represented in the oeis) will lead to a somewhat interesting sequence. 
Considering the surprising (to me at least) length of some of the a(*) being
discovered just up to 100, especially at 10, 20, 96, and 98, I think this sequence is interesting enough to beg another question: Just how random are the digitis of pi really? If we were to generate oher such "random" sequences (perhaps the digits of e as transcendental or sqrt 2 as merely irrational but nonpatterned), seeing similar prime subsequence patterns might make this worthy of number theoretical study. In any case, as merely observor now, may I ask: Is iit very hard to prove the biggest PRPs prime? What's the L&L accreditor you referred to? Is a(20) still chugging away? Thanks for all your great work. 
[QUOTE=Batalov;309040]E.W.W.'s [URL="http://mathworld.wolfram.com/PiPrime.html"]mention[/URL] of the upper search limit is 6 years old[/QUOTE]
He since increased it to 127,523 if I read this correctly: [url]http://mathworld.wolfram.com/IntegerSequencePrimes.html[/url] 
[QUOTE=CRGreathouse;312351]He since increased it to 127,523 if I read this correctly:
[URL]http://mathworld.wolfram.com/IntegerSequencePrimes.html[/URL][/QUOTE] 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)? 
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: [CODE]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 } [/CODE] 
[QUOTE=Batalov;313775]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: [CODE]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 } [/CODE][/QUOTE] 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 preinitialized  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. 
1 Attachment(s)
This is just a replacement shippet of the full code (which was posted earlier), where $p is a long string with 250000 digits of [TEX]\pi[/TEX]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.
[QUOTE=Batalov;308790]Well, ok, records are made to be broken. With a bit of luck I found a 140,165digit 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 [I]may[/I] not be a minimal solution: ...[/QUOTE] a(96) is doublechecked (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. 
Does anyone think this series is oeisworthy?
As OP I'm not entitled to an opinion. But some of those PRPs batalov discovered are eyeworthy, I think. Maybe when a(20) is finally tackled ... 
[QUOTE]
a(96) is doublechecked (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.[/QUOTE]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)? 
Generate your Pi with [url=http://www.numberworld.org/digits/Pi/]ycruncher[/url].

Wouldn't want to crunch too many y''s, they're rare enough.
I see the first 20 occurs at digit 53. Thanks. 
1 Attachment(s)
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, MR with bases 3 and 5, and the FrobeniusUnderwood 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 'Pi2M.txt' file I used ycruncher, 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 [COLOR=DarkOrchid][Digressions ahead][/COLOR] 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: [FONT=Courier New] 5m 50s PFGW (Fermat) 6m 15s PFGW (Fstrong) 26m 30s PFGW (Fermat and [COLOR=DarkSlateGray]Lucas[/COLOR] PRP) 30m 15s MPU::GMP is_strong_pseudoprime($n,2) (1 [COLOR=DarkGreen]MR[/COLOR]) 63m 40s Pari 2.6.1 ispseudoprime($n,1) (1 [COLOR=DarkGreen]MR[/COLOR]) 85m 45s MPU::GMP ES [COLOR=DarkSlateGray]Lucas[/COLOR] test 90m 15s MPU::GMP FrobeniusUnderwood test 115m 55s MPU::GMP is_prob_prime (ES [COLOR=Navy]BPSW[/COLOR]) 127m 0s MPU::GMP strong [COLOR=DarkSlateGray]Lucas[/COLOR] test 206m 20s mpz_prp is_strongbpsw_prime (S [COLOR=Navy]BPSW[/COLOR]) 213m 15s Pari 2.6.2 ispseudoprime($n) (AES [COLOR=Navy]BPSW[/COLOR]) [/FONT] It's much closer at 10k digits. Also until we hit the PRP at this range basically everything would be found composite by the SPSP2 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. 
1 Attachment(s)
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... :blush: 
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. 
Nice work. However, extending the sequence to higher starters is not big deal, as the most of them are "easy".
Both "with initial 3" and "without" were discussed before, this does not change the things too much, so we decided to let the 3 out of it. Also, the problem asks for primes which "extends" the initial starting number. There is not so much fun to say that the prime starting with 3 is 3, or the one starting with 17 is 17. (see [URL="http://www.mersenneforum.org/showpost.php?p=308871&postcount=45"]post #45[/URL], onwards). The only interesting case remaining after Batalov's work is actually "20". Who can solve the 20 gets a bonus... :smile: Beside of it, the 10, [URL="http://factorization.ath.cx/index.php?id=1100000000530947423"] 17,[/URL] 80, 81, 84, 96 need to be proved prime in factorDB (they are only PRP; the 54, 62, 73, 97 were already proved prime). This is secondary. The main goal remains 20. 
[QUOTE=LaurV;351795]Nice work. However, extending the sequence to higher starters is not big deal, as the most of them are "easy".[/QUOTE]But there are 8 more in his results that are indicated at 170k+ digits or more, so not all are easy.
[quote]Both "with initial 3" and "without" were discussed before, this does not change the things too much, so we decided to let the 3 out of it.[/quote]The scripts and discussion on page 3 use the initial 3. davar's post on page 3 indicates "Indexing could begin with the 3 as 1 or 0" meaning the 3 was intended to count. davar's post on page 5 also indicates 3 is included. Batalov's script on page 5 Batalov's script isn't entirely clear, but if the output file is untouched it has "3.14..." in it meaning it wouldn't catch the initial 3 because of the decimal point left in. Your results on page 5 leave them out. I don't think this was discussed. People seem to have just picked something and sometimes mention what they chose. The original poster twice indicated the 3 should be included. I think it's a terrible sequence if we have 4 different versions. [quote]Also, the problem asks for primes which "extends" the initial starting number. There is not so much fun to say that the prime starting with 3 is 3, or the one starting with 17 is 17. (see [URL="http://www.mersenneforum.org/showpost.php?p=308871&postcount=45"]post #45[/URL], onwards).[/quote]The original post is misleading in that it says find the number then find "the first prime constructed from the subsequent digits". So for 1 you should find the 1, then choose "41" since that is the first prime made from subsequent digits. But we all know that wasn't what was meant. We want the prime made from the first occurrence of the number concatenated with the fewest [[I]positive[/I]] number of subsequent digits. Without "positive" we would accept 0 additional digits, otherwise not. The "uninteresting" bit came from [URL="http://mersenneforum.org/showpost.php?p=305563&postcount=29"]post 29[/URL] rather than 45. What I meant by saying that if we extend the series this becomes less important, is that sure, we find "7" for 7, but go a little farther and we'll find each 7x, and later 7xx, etc. I don't particularly care which one is chosen, but it would be nice if we all actually worked on the same sequence. [quote]The only interesting case remaining after Batalov's work is actually "20". Who can solve the 20 gets a bonus... :smile:[/quote]The only interesting case up to 100, you mean. Did you look at JF's post? 20 would certainly be nice to solve. If only I had more spare computers :) I got most of what I wanted from it  a nice speedup of my pretest for large (50k+ digit) numbers. I'll probably run a(20) farther later, but someone else will likely beat me to it. I can run primo on 17, 81, and 84, but 10, 80, and 96 look daunting. 
Grrr... I have to write you down in my book under the chapter "people not to argue with, ever!".
[COLOR=White](that was a compliment, told with much respect. don't get fussy about it!) [/COLOR] 
:( Sorry.

Danaj, errors corrected, thanks!
The list in the first post doesn't include the leading 3, and for 2 and 3 results are equal to the number, so I just used this ruleset. Appending digits to prime starting numbers or not doesn't really matter, the information is still there. Example: result for a(2) is either 2, or the same als a(26). No need to calculate anything new, just rearrange the list. 
The value "31415926" occurs at position 50366471 ("3." not counted) of pi.
No longer value of this pilike number in the first 1e9 decimal digits of pi. 
"314159265" occurs at position 1660042750. I didn't find the next value in the first 5000M digits.
The current list in the first post may or may not include the first 3  the only number starting with 3 listed is "3" with no starting position noted. It looks like almost all the OEIS pi/prime related series include the beginning 3, e.g. [URL="http://mathworld.wolfram.com/PiPrime.html"]PiPrime[/URL] (OEIS [URL="http://oeis.org/A005042"]A005042[/URL]) and all the crossref'd entries it has. I agree with you (JF) on the uninteresting bit. At first I thought it was a good change, but now I think it just adds complication that doesn't really add value. As you point out if a(2) is boring, just go to a(26) for the interesting part. If a(41) is boring, look at a(415). 
1 Attachment(s)
some Update: Increasing run time and decreasing chance
per PRPtest have dampened my enthusiasm a bit, so I did cut back from 34 cores nearly 24/7 to 2 cores parttime. #20 passed 356K digits, still no luck. A friend is donating 1 core parttime working on #196, passed 250K digits. The other 6 unsolved up to 1111 (#380, #422, #861, #899, #955 and #988) are brought to 200K digits and parked for now. Topic leading 3 or not: for most starting values this will do nothing except shifting their offset by 1. The others will lead to OEIS A005042. Again, not really information gained/lost. 
[QUOTE=bsquared;305025]IANANT, but the infinite sum of 1/ln(n) diverges, so even accounting for the fact that on average we only sum 4 of every 10 terms, I would think that the probability that there exists a prime would be 1.[/QUOTE]
This would also appear to follow if the digits are [url=http://en.wikipedia.org/wiki/Normal_number]normal[/url], which is generally believed but as yet unproven. If normality holds, the digits will further be "as random as can be", but note the above 2 properties will be true of all normal reals, which are (provably) a dense subset of the reals. Interestingly, the normals likely include both irrationals and transcendentals  for example, sqrt(2), pi and e are all generally believed (but not proven) to be normal. I find it interesting that is far easier to prove that almost all reals are normal than to prove that a selected one, even one as wellstudied as sqrt(2), is. 
Just wondering if any progress has been made in this series,
especially a(20)? 
a(20) neares 450k digits, still nothing
a(196) finished with a 312306digit PRP 
[QUOTE=J F;383738]a(20) neares 450k digits, still nothing
a(196) finished with a 312306digit PRP[/QUOTE] Re: a(20) at 450K: what's the probability at this point that it will reach or exceed 1M digits ? If so, how expensive will it be to check that far ? 
[QUOTE=davar55;383775]Re: a(20) at 450K: what's the probability at this point that
it will reach or exceed 1M digits ? If so, how expensive will it be to check that far ?[/QUOTE] Quick and dirty calculation, chance for (at least) one PRP from 450K to 500K 45%, 500K to 1M ballpark 25%. That doesn't sound too bad, but the required corehours ARE bad! With PFGW a PRPtest at 450K digits takes ~2.5h on an older nonAVX I5750 core, 900K digits would be ~10h, a modern AVXcore is a bit less than half that time. Many thousand of them after TF (+TF time)  there you go. 
Thanks. Will this computation be continuing indefinitely, or is there
some software limit, or a time budget? I think we'll need a(20) to have a satisfactory entry in oeis, if that's deemed ok. 
[QUOTE=ewmayer;358683]This would also appear to follow if the digits are [URL="http://en.wikipedia.org/wiki/Normal_number"]normal[/URL], which is generally believed but as yet unproven.
If normality holds, the digits will further be "as random as can be", but note the above 2 properties will be true of all normal reals, which are (provably) a dense subset of the reals. Interestingly, the normals likely include both irrationals and transcendentals  for example, sqrt(2), pi and e are all generally believed (but not proven) to be normal. I find it interesting that is far easier to prove that almost all reals are normal than to prove that a selected one, even one as wellstudied as sqrt(2), is.[/QUOTE] For pi, e and sqrt(2), is there any evidence beyond empirical observation of the sofar known digits that addresses their normality, i.e. other than statistics? Are there any positive results toward this? I too "generally believe" they are normal, but looking at the first say trillion digits of sqrt(2) is still subject to the law of small numbers considering the infinity of its nonrepetitiveness. 
I was very excited when I thought of the OP question. In attacking the
question by hand and with my calculator, I anticipated some very long primes coming out of the digits of pi. Now I eagerly await a(20). 
In preparation for a possible oeis entry, and since the PRPs here were not posted,
could someone post a list of the first 99 (01 thru 99) elements of this sequence? Each line as: xxx > # where xxx is the index (001 thru 099) and # is either the prime, PRP### followed by abcde.....vwxyz (the end digits), or "no such prime". (If you want to improve on this format, fine.) 
[QUOTE=davar55;390038]...and since the PRPs here were not posted...[/QUOTE]
?? Some outdated limits for the unfinished numbers and finished #196 aside, what's wrong with the list in post 74? Completely off topic: can someone recommend a program or efficient way to cut down an arbitrary integer to a shorter representation? Let's say I have a 1M digit number and want it down to a 30? 20? chars term of form a*b^c+d. As short as possible with 'reasonable' (minutes? no idea about the complexity) CPU time. Thanks in advance. 
Obviously it will nearly always not be possible to get such a representation, but I'd be tempted to use the linearforms stuff in Pari on log(N) and logs of enough small numbers to try to fit A,B,C, then figure out D by subtraction.
[code] lp=[];forprime(p=2,200,lp=concat(lp,[log(p)])) lindep(concat([log(861*136^997+142857)],lp)) [/code] 312ms to recognise 85*53^226911 using primes up to 100 (with realprecision=500); 2152ms using primes up to 200; 5512ms for primes up to 300; you get a nonsparse vector if it didn't work. 
[QUOTE=J F;390274]Completely off topic: can someone recommend a program or
efficient way to cut down an arbitrary integer to a shorter representation? Let's say I have a 1M digit number and want it down to a 30? 20? chars term of form a*b^c+d. As short as possible with 'reasonable' (minutes? no idea about the complexity) CPU time. Thanks in advance.[/QUOTE] Simple informationtheoretic reasoning suggests what you want cannot be done (i.e, compressing an [B]arbitrary[/B] integer). If it could be done, you've just found out the world's most efficient compression algorithm :shock: 
Shame  talk about obvious, I could have come up
with this myself... I had some muddy thoughts similiar to Mr. Fivemack, with X=a*b^c+d try to puzzle the logs together to come close up to log(X) and the add/substract 'the rest'. At this moment I just didn't think about that this is trying to map a set 1:1 to a much smaller set. *in the corner, with red ears* Thanks for the replys 
[QUOTE=J F;390274]??
Some outdated limits for the unfinished numbers and finished #196 aside, what's wrong with the list in post 74? ... Thanks in advance.[/QUOTE] Your welcome (OP). 
[QUOTE=davar55;304822]Finding primes in the digits of pi has been done,
so here is yet another primes in pi puzzle. For every positive integer n (in decimal) find the first occurrence in pi of the digits of that integer, then the first prime constructed from the subsequent digits of pi. Here's what I had in mind: __________________________________ 1 > 14159 2 > 2 [STRIKE]26535897932384626433[/STRIKE] (*) 3 > 3 4 > 41 5 > 59 (*) 6 > 653 7 > 79 (*) 8 > 89 9 > 9265358[COLOR=sienna]97[/COLOR]9323 [COLOR=darkred](or 97 ??)[/COLOR] 10 > [COLOR=#8b0000]102701 [COLOR=black](or[/COLOR] [/COLOR][COLOR=darkred]1058209749...6531873029[/COLOR][SUB]<19128>[/SUB] ?) (PRP) 11 > 11 12 > 12847564823 (or[COLOR=#8b0000] 12848111...678925903[/COLOR][SUB]<211>[/SUB] ?) ... [COLOR=green]20 > [COLOR=darkred](...more than 215000digit...)[/COLOR][/COLOR] [COLOR=green][COLOR=darkred]...[/COLOR] 62 > 3490digit Prime (and three more PRPs) 80 > 41938digit PRP. 81 > 4834digit PRP. 84 > 3057digit PRP. 96 > [B][COLOR=darkred]140165digit PRP[/COLOR][/B]. 98 > 61303digit PRP.[/COLOR] [COLOR=black]up to 100 (except 20): all primes/PRPs are less than 1000digits or shown above[/COLOR] __________________________________ (*) of course 2, 5 and 7 are prime (**) My calculator only checks for small factors, so * and ** may not actually be prime I think the list carried to (at least) 100 will possibly contain some more interestingly large primes, or will the primechecking facility be tested only by going to 1000, or beyond? _______________ [COLOR=darkred]P.S. I could restore the original values for 2 and 10, but ... they were composite. You can easily see the original in post #2 (SB)[/COLOR][/QUOTE] In the OP, I had to enter the digits of pi by hand into my calculator, and let it test for primality. That procedure was errorprone, hence the wrong values for 2 (extended from the true value of 2) amd 10. But I hurried to get my partial results out, because I knew the forum would do the calculations over. I think this will be an important sequence and jumping off point  we'll see. 
3.14159 2654
And that's all I know. The primes There are 2 3 5 7. And there are more. Thank you very much for starting this thread Regards Matt 
I've just noticed:
the series as computed (but not as in post#74) can be used to reconstruct the digits of pi, as the first occurrence of the positive integers in pi exhaust pi as the sequence of integers progresses. there is overlap, as in the first 3 (intended to be the lead 3) and the first 31 (also from 3.1) and the first 314 (which can be reconstructed from the 314th prime in the series (which starts with 314... ). hence we should probably index the lead 3 as index 0 of the digits of pi. this loses no primes, they just appear later in the series. also, when we confirm the first prp of a(20), this reconstruction of pi from the output would allow a double check of both the digits of pi and all the intermediate primes. this assumes: For any positive integer written in decimal it is possible to construct a prime number by concatenating some finite sequence of decimal digits at its end. which is certainly true. 
It's been a while. Any new results ?
Has a(20) been resolved with a prime, or probable prime, or has anyone tried proving that a(20) never produces a prime ? Any other big results below a(1000) ? 
Any resolution of a(20)?
How long does each PRP check take at 450K? 
[QUOTE=davar55;398758]Any resolution of a(20)?
How long does each PRP check take at 450K?[/QUOTE] Hate being a pest but I'm really into this result. Can you say how high a(20) has been tested? :geek: 
[QUOTE=davar55;399890]Hate being a pest but I'm really into this result.
Can you say how high a(20) has been tested? :geek:[/QUOTE] Is anyone here still working on this one? 
[QUOTE=davar55;401142]Is anyone here still working on this one?[/QUOTE]
first thing that comes to mind is pari and using say FaR or my attempt at parvecsearch ( see pari commands thread) but with alteration and depending on which gets used to look for all primes in a given range that start with that and searching for them in parallel or something like that. 
[QUOTE=science_man_88;401178]first thing that comes to mind is pari and using say FaR or my attempt at parvecsearch ( see pari commands thread) but with alteration and depending on which gets used to look for all primes in a given range that start with that and searching for them in parallel or something like that.[/QUOTE]
See post 64 for some timings once the size gets large. Pari is 10 times slower than PFGW once the sizes get very large. One still needs to run something like BPSW on the result (e.g. Perl/ntheory, Pari, or WraithX mpz_prp), but that ought to be faster than using Pari for each value. 
All times are UTC. The time now is 15:09. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2021, Jelsoft Enterprises Ltd.