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

 davar55 2012-07-15 18:51

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 215000-digit...)[/COLOR][/COLOR]
[COLOR=green][COLOR=darkred]...[/COLOR]
62 --> 3490-digit Prime (and three more PRPs)
80 --> 41938-digit PRP.
81 --> 4834-digit PRP.
84 --> 3057-digit PRP.
96 --> [B][COLOR=darkred]140165-digit PRP[/COLOR][/B].
98 --> 61303-digit PRP.[/COLOR]
[COLOR=black]up to 100 (except 20): all primes/PRPs are less than 1000-digits 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 prime-checking 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]

 xilman 2012-07-15 19:07

[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 prime-checking facility be tested only by going to 1000, or beyond?[/QUOTE]Another, related problem, would be to to find the first radix-n representation of primes in the radix-n representation of \pi which begin with the digit n-1 for all integer n >=2.

Alternatively, those primes which begin with each of the digits <n in the radix-n representation of the primes and of \pi

Paul

 patrik 2012-07-15 20:16

26535897932384626433 = 150917801 x 175830139033
1058209749445923078164062862089986280348253421170679821480865132823 = 196699 x 1834313671 x 4817619413830406641955201 x 608784400187359263779612387

 Batalov 2012-07-15 20:48

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

 Batalov 2012-07-15 23:47

There shouldn't be a probabilistic argument, really. (Silly me.)

On one hand, these candidates are not sparser than any quasi/near-repunits (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 19128-digit 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.

 davar55 2012-07-16 03:35

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.

 Batalov 2012-07-16 04:00

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 50-digit prime, but then again, the mere "2" is already prime.

 bearnol 2012-07-16 12:44

You're aware that the first prime-instance might not necessarily start at the first instance?
(this is the same mistake as Shallit made)
J

 henryzz 2012-07-16 13:59

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+offset-1))%(10^2))==n,
for (digits=2, 1000,
f=factor(floor(Pi*10^(digits+offset-1))%(10^digits),9);
if (matsize(f)==[1,2],
if (ispseudoprime(floor(Pi*10^(digits+offset-1))%(10^digits),20),
print(floor(Pi*10^(digits+offset-1))%(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 10-99 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.

 xilman 2012-07-16 15:55

[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

 Batalov 2012-07-16 18:43

[QUOTE=bearnol;304883]You're aware that the first prime-instance 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^n-1 or in 2) 8579*10^n-1. (subsequences of pi would be obviously harder)

[SPOILER]Yes, 2) is a trick proposition. There exists a prime.[/SPOILER]

All times are UTC. The time now is 03:26.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.