mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Puzzles (https://www.mersenneforum.org/forumdisplay.php?f=18)
-   -   Primes in order in pi (https://www.mersenneforum.org/showthread.php?t=27551)

 robert44444uk 2022-02-04 15:54

Primes in order in pi

2 Attachment(s)
I am a little surprised I can't find any mention on the web, of the sequence of primes, in order, that might be found in the decimal expansion of pi (3.1415926535..)

The first instance of 2 is at the 6th decimal position, the first 3 thereafter at the 9th position, the first 5 thereafter at the 10th, etc.

For definition's sake, the first 71 is not at the 1757th position following 67 at the 1756th, as the 1757th position was also used to ascertain 67. Instead, 71 is found at the 1923rd.

A file of the decimal positions of all primes up to 8713 which are to be found in order in the first 10,000,000 decimal positions of pi is attached.

A graph is also shown, showing the positions of each prime, supporting the hypothesis that pi is normal. Some of the results are shown below

[CODE]
14159[COLOR="Red"]2[/COLOR]65[COLOR="red"]35[/COLOR]89[COLOR="red"]7[/COLOR]93238462643383279502884197169399375105820974944592307816406286208998628034825342[COLOR="red"]11[/COLOR]70679821480865[COLOR="red"]13[/COLOR]28230664709384460955058223[COLOR="red"]17[/COLOR]2535940812848111745028410270[COLOR="red"]19[/COLOR]38521105559644622948954930381964428810975665933446128475648[COLOR="red"]23[/COLOR]378678316527...
[/CODE]

The calculation is trivial. My average 7 year old desktop carried out the following perl program in less than 10 seconds.

[CODE]
#!/usr/bin/env perl
use warnings;
use strict;
use Math::Prime::Util qw/:all/;
use feature ':5.10';

\$|=1;

my \$pie = substr(Pi(10_000_000),2);
my \$maxprime = 100_000;
my \$prevplace = 0;
forprimes {
my \$i = 1+index(\$pie,\$_,\$prevplace);
say \$_, " ", \$i;
\$prevplace = \$i+length(\$_)-1;
if ( \$i==0){
last;
}
} 2,\$maxprime;

[/CODE]

So...the challenge (as this is the puzzle subsection) is to expand the series, and perhaps find quite large gaps or close instances..and post to OEIS

 Uncwilly 2022-02-04 16:29

That inflection point around 1000 looks interesting. Any insight into that?

 robert44444uk 2022-02-04 17:04

[QUOTE=Uncwilly;599389]That inflection point around 1000 looks interesting. Any insight into that?[/QUOTE]

That's the point at which the next prime has 4 digits. There would be similar inflections at 2 to 3 and 1 to 2 digits as well.

When I inferred that pi is normal in the OP, I meant pi behaves as a normal number.

 newalex 2022-02-05 01:48

1 Attachment(s)
Here is my result for 100b digits of Pi.
All primes up to 1042333 were found in order in these 100b digits.

 Dr Sardonicus 2022-02-05 14:50

Assume pi is a normal number to base ten.

It occurred to me to wonder how many times the block of decimal digits representing a prime p can reasonably be expected to occur before it occurs in its proper place in the sequence of primes.

 kruoli 2022-02-05 14:59

[QUOTE=newalex;599414]Here is my result for 100b digits of Pi.
All primes up to 1042333 were found in order in these 100b digits.[/QUOTE]

Would you mind sharing/PM'ing your program? I could run it on 1t digits I have. And maybe some other constants.

 newalex 2022-02-05 17:05

[QUOTE=kruoli;599438]Would you mind sharing/PM'ing your program? I could run it on 1t digits I have. And maybe some other constants.[/QUOTE]
Yes, of course. But I am not sure if it would be suitable for you. It is written in Java and stores all digits in memory. So you need 1 Tb of RAM to run it for 1t. It can be fixed easily but need some work.
Here is the source code
[CODE]import java.io.*;

public class PrimesInPi {

public static void main(String[] args) throws IOException {
long piSize = 100000000000L;
final int maxArraySize = 1000000000;
int chunkSize = (piSize>maxArraySize) ? maxArraySize : (int) piSize;
char[][] pi;
pi = new char[(int) (piSize/chunkSize)][chunkSize];
for (int i=0; i<piSize/chunkSize; i++) {
}
fr.close();
FileWriter result = new FileWriter("output.txt");
long pos = 0;
int i=0, j=0;
while (pos<piSize) {
if (isCurrentPrime(pi, prime, i, j)) {
result.write(prime+" "+(pos+1)+"\n");
j+=prime.length();
pos+=prime.length();
if (j>=chunkSize) {
j-=chunkSize;
i++;
}
} else {
pos++;
j++;
if (j==chunkSize) {
j=0;
i++;
}
}
}
result.close();
}

private static boolean isCurrentPrime(char[][] pi, String prime, int i, int j) {
boolean result = true;
int i1 = i, j1 = j;
for (int k=0; k<prime.length(); k++) {
if (prime.charAt(k) == pi[i1][j1]) {
j1++;
if (j1 == pi[i1].length) {
j1 = 0;
i1++;
}
if (i1 == pi.length) {
result = false;
break;
}
} else {
result = false;
break;
}
}
return result;
}
}[/CODE]
The program expects to have pi.txt and primes.txt files in the same folder. It ignores first 2 symbols in pi.txt file to start from fraction part(assuming the file starts with 3. ). primes.txt is a list of primes(one line - one prime).
piSize variable should set to count of pi digits which we want to process.

 kruoli 2022-02-05 17:16

Thank you! :smile:

For some reason I was expecting that the straightforward approach would be inefficient but you are correct that this approach can be applied to a file that is not fully stored in memory. I'll code up something later. I like your idea to have the primes precalculated in a file. This makes the code way less complex.

 uau 2022-02-05 17:59

[QUOTE=Dr Sardonicus;599436]It occurred to me to wonder how many times the block of decimal digits representing a prime p can reasonably be expected to occur before it occurs in its proper place in the sequence of primes.[/QUOTE]
Each sequence of n digits should occur equally often. Thus if you sequentially search for 50 6-digit sequences, you should on average expect to have seen 50 of the last sequence - on average encountering it once before finding each of the earlier 49 ones.

So the expected number should be (number of earlier equally long target sequences) + (number of one earlier one digit shorter target sequences)/10 + (two shorter)/100 and so on.

 robert44444uk 2022-02-07 09:15

You have to love the projected result of this exercise - there is exists within the decimal representation of pi, (which is itself just one of an infinite number of irrationals), all of the infinity of primes, in order.

I would expect that this projected result will be the same for all integer bases, i.e. the representations of the primes in any integer base can be found in order within the representation of pi in that base. I can almost visualise this must be true for base 2.

Can we go further to project or hypothesise that the primes, as depicted in any integer base are in order in the representation of [U]any [/U]irrational number in the same integer base?

As integers represented in irrational bases appear themselves irrational, then we can safely say that the primes in order, represented in irrational base form, cannot be found in the representation of the irrational in that base, as the irrational in its own base will have a simple non-irrational form.

Because the representation of the irrational form is infinite, I would hypothesise that the primes represented in irrational base form (which I think are irrational representations themselves) are not included in order in the representation of an irrational number presented in an different rational or irrational base.

Have I covered all the permutations here?

PS: My teacher at school did day "don't mess with infinity, it bites"

 uau 2022-02-07 12:11

[QUOTE=robert44444uk;599572]You have to love the projected result of this exercise - there is exists within the decimal representation of pi, (which is itself just one of an infinite number of irrationals), all of the infinity of primes, in order.[/QUOTE]
I don't find it too interesting myself. Any random sequence would eventually produce a match. So would a sequence like 1 2 3 4 5 ... (you would get more matches arbitrarily late as parts of larger numbers).

[QUOTE]Can we go further to project or hypothesise that the primes, as depicted in any integer base are in order in the representation of [U]any [/U]irrational number in the same integer base?[/QUOTE]No, you can easily construct an irrational number whose decimal representation consists of only 0 and 1.

 robert44444uk 2022-02-07 12:36

[QUOTE=uau;599581]

No, you can easily construct an irrational number whose decimal representation consists of only 0 and 1.[/QUOTE]

Hah, silly me

 kruoli 2022-02-12 22:42

1 Attachment(s)
Appended is what I have got up to one trillion digits.

 chalsall 2022-02-13 01:13

[QUOTE=kruoli;599950]Appended is what I have got up to one trillion digits.[/QUOTE]

Seems to be a reasonable sample set. Thank you for that. Sincerely.

 robert44444uk 2022-02-14 18:53

[QUOTE=kruoli;599950]Appended is what I have got up to one trillion digits.[/QUOTE]

Amazing work. But...You numbers overlap I notice - see the results for 67 and 73. In my original definition I disallowed overlaps.

 kruoli 2022-02-15 10:17

This is correct, I overlooked it. I will run it again with this rule in mind.

 kruoli 2022-02-16 10:33

1 Attachment(s)
These are my updated results. The only indices that changed are those of 71, 73 and all primes in the range 53567-57173. The first two are known from the example in the first post of this thread, the other one is because of the digits …53653657… starting at position 429,388,878, which includes both primes 53653 and 53657.

 robert44444uk 2022-02-16 16:53

The series includes a couple of large adjacent primes, at the positions shown

889673 and 889687 at position 61984722855
979291 and 979313 at position 68361333199

This contrasts the very long wait for 1184363 - no less than a 161684719 digit wait

1184357 202059128456
1184363 202220813175

 All times are UTC. The time now is 07:48.