Problems & Puzzles:
Puzzles
Puzzle 253. Eureka?
Someone too shy (?) selfnamed '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 twodigit prime must end in 1,
3, 7, or 9. There are only 10 twodigit primes using these numbers: 11 13
17 19 31 37 71 73 79 97. Arranging all these numbers into one will produce
an 11digit number, which could also be a 12digit 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. Bruteforcing 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 Ddigit 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
***
