Problems & Puzzles: Puzzles

Puzzle 253.  Eureka?

Someone too shy (?) self-named 'Eureka' submitted the following Curio to the well know site maintained by Caldwell and Honaker (Prime Curios!):

619737131179 is the largest known prime such that any two adjacent digits are distinct primes.

1. Show that this statement is improper.

2. What is the largest prime such that any three adjacent digits are distinct primes?

Solution:

Contributions came for Luke Pebody, Ray Opao and J. K. Andersen:

Luke wrote:

1. 619737131179 is the largest number such that any two adjacent digits are distinct primes. I'll try and find a nice proof...

2. 9419919379719113739773313173 (28 digits) is the largest prime such that any three adjacent digits are distinct primes... 9551979199733313739311933719319133 (34 digits) is the largest prime such that any four adjacent digits are distinct primes... 374831379939791939113997931991393133317939371999713 (51 digits) is the largest prime such that any five adjacent digits are distinct primes.

***

Ray wrote:

1. The statement requires that any two adjacent digits must be distinct primes. A two-digit prime must end in 1, 3, 7, or 9. There are only 10 two-digit primes using these numbers: 11 13 17 19 31 37 71 73 79 97. Arranging all these numbers into one will produce an 11-digit number, which could also be a 12-digit number if the leftmost digit and an even digit form a prime. Hence, the largest possible prime would have at most 12 digits. Stating that it is the largest "known" prime implies the possibility of finding another greater prime, which is actually not possible as this is already the largest. Brute-forcing using WinPFGW also yields the same result.

2. 3 adjacent digits: 9419919379719113739773313173... It could actually be generalized that the largest prime such that D adjacent digits are distinct primes has at most N+D digits, given that N is the number of D-digit primes that use only the digits 1, 3, 7, or 9...

***

J. K. Andersen wrote:

1. Exhaustive search shows 619737131179 is the largest existing prime, so "known" can be omitted.

2. I allow leading 0's in the adjacent digits. Exhaustive search has found the following maximal primes, all proved.

For 3 digits: 9419919379719113739773313173
For 4 digits: 9551979199733313739311933719319133
For 5 digits: 763031379939791939113997931991393133317939371999719
For 6 digits: 9651473911777911173191173713117119
For 7 digits: 99071479791317917331771937311
For 8 digits: 6195066779711393117319331177319

3. If leading 0's are not allowed:

For 5 digits: 374831379939791939113997931991393133317939371999713
For 7 digits: 91447877797191131131113193717
For 8 digits: 336387433799771731391119319917

***

 Records   |  Conjectures  |  Problems  |  Puzzles