mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2012-07-16, 20:54   #12
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

216478 Posts
Default

For 62, the PRP is 3490-digit.
For 81, the PRP is 4834-digit.
For 84, the PRP is 3057-digit.

(these would be easy to prove prime)

Last fiddled with by Batalov on 2012-07-16 at 21:08
Batalov is offline   Reply With Quote
Old 2012-07-16, 21:22   #13
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2×2,861 Posts
Default

Quote:
Originally Posted by Batalov View Post
For 62, the PRP is 3490-digit.
For 81, the PRP is 4834-digit.
For 84, the PRP is 3057-digit.

(these would be easy to prove prime)
How far are you testing?
henryzz is offline   Reply With Quote
Old 2012-07-16, 21:25   #14
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

9,127 Posts
Default

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.

Last fiddled with by Batalov on 2012-07-17 at 02:43
Batalov is offline   Reply With Quote
Old 2012-07-17, 07:17   #15
Random Poster
 
Random Poster's Avatar
 
Dec 2008

179 Posts
Default

Quote:
Originally Posted by Batalov View Post
Would you care to expand on this?
How would you move on from the first instance to the next one?
By proof?
By using a not-completely-insane 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).
Random Poster is offline   Reply With Quote
Old 2012-07-17, 07:57   #16
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

9,127 Posts
Default

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
58209749445923078164062862089986280348253421170679
82148086513282306647093844609550582231725359408128
48111745028410270193852110555964462294895493038196...
Suppose we've checked the substrings starting from the red 20 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 20, find 2089 and say that we are done.
We can only move on to the next instance of the starting point after we have proven that there are no primes formed by the first instance. Can we prove that?
Batalov is offline   Reply With Quote
Old 2012-07-17, 08:21   #17
axn
 
axn's Avatar
 
Jun 2003

22×52×47 Posts
Default

Do you (the general "you") define the "first prime instance" using the starting position or the ending position?

Explicit clarification is called for.
axn is offline   Reply With Quote
Old 2012-07-17, 08:29   #18
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

9,127 Posts
Default

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 5-6-digit values. Too easy.

Indeed, I am interested in the hard variant (For a given number n, find the leftmost instance of a prime substring in decimal expansion of pi that starts with n.) 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

Last fiddled with by Batalov on 2012-07-17 at 08:44
Batalov is offline   Reply With Quote
Old 2012-07-17, 15:14   #19
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

37×89 Posts
Default

Quote:
Originally Posted by Batalov View Post
T
We can only move on to the next instance of the starting point after we have proven that there are no primes formed by the first instance. Can we prove that?
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.

Last fiddled with by bsquared on 2012-07-17 at 15:15
bsquared is online now   Reply With Quote
Old 2012-07-17, 18:26   #20
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

9,127 Posts
Default

80 -> 8034825342...6216977871<41938>

Formula: floor(Pi*10^42021)%(10^41938). (Submitted to Lifchitz&Lifchitz...)

edit: I just put my $0.25 in the swear jar. B->

Last fiddled with by Batalov on 2012-07-18 at 01:01 Reason: Formula
Batalov is offline   Reply With Quote
Old 2012-07-17, 20:42   #21
davar55
 
davar55's Avatar
 
May 2004
New York City

102068 Posts
Default

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.
davar55 is offline   Reply With Quote
Old 2012-07-18, 03:00   #22
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×29×83 Posts
Default

I Am Not A National Treasure???
Dubslow is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Mersenne Primes p which are in a set of twin primes is finite? carpetpool Miscellaneous Math 3 2017-08-10 13:47
Distribution of Mersenne primes before and after couples of primes found emily Math 34 2017-07-16 18:44
Conjecture about Mersenne primes and non-primes v2 Mickey1 Miscellaneous Math 1 2013-05-30 12:32
A conjecture about Mersenne primes and non-primes Unregistered Information & Answers 0 2011-01-31 15:41
possible primes (real primes & poss.prime products) troels munkner Miscellaneous Math 4 2006-06-02 08:35

All times are UTC. The time now is 16:47.

Wed Sep 30 16:47:14 UTC 2020 up 20 days, 13:58, 0 users, load averages: 1.83, 1.82, 1.78

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

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.