1
$\begingroup$

What is the largest number, which can built as a sequence (from left to right) of different two-digit primes only? For example, 1371731 is valid, 137131 is invalid (containing 13 twice), 139717 is invalid (containing non-prime 39)

$\endgroup$
2
  • $\begingroup$ If there's some clever way to solve this problem without a brute force search, I'll be happy to retract the VTC. (I couldn't think of a way, but that doesn't mean it doesn't exist.) $\endgroup$ – Bass Jan 22 at 13:37
  • $\begingroup$ @Bass: it is easy to see, that all interior two-digit primes have only digits 1,3,7,9 and those can be used as vertices of a directed graph. If we can get 1 as the first interior digit, we can continue with a greedily approach. For example, 1979 doesn'work, so we take 1973, but stuck again at 197379. So back to 197371 .... $\endgroup$ – ThomasL Jan 22 at 20:51
2
$\begingroup$

I'm not sure how I'd prove this is optimal, but my answer is:

a 12 digit number; there at least two, maybe more, but the one I came up with first was 411379717319 (611379717319 also works)

Reasoning:

Since no two-digit prime numbers end in 2, 4, 5, 6, or 8, to maximize the length of the resulting number, it should begin with one of these. Since the beginning of one prime is the beginning of the next, after the first 2 digit number, we can't use any numbers that start those digits either (with the exception of the first), giving us 11, 13, 17, 19, 31, 37, 71, 73, 79, and 97 to play with. Since there's two numbers that end with "9" and only one that begins with it, I knew that the number should end with "9", but other than that it was just trial-and-error getting them in a plausible order (I got lucky the first time) yielding me 411379717319 (41, 11, 13, 37, 79, 97, 71, 17, 73, 31, 19).

$\endgroup$
2
$\begingroup$

The maximum length is

12

attained by

411971731379

There are 192 numbers with this maximum number of digits, and the largest of these is

619737131179

All of them start with

41 or 61

All of them end with

19 or 79

$\endgroup$
2
  • $\begingroup$ I read "largest" as "longest", so yours is actually the correct answer XD $\endgroup$ – samm82 Jan 21 at 21:04
  • 1
    $\begingroup$ That was my initial interpretation as well. $\endgroup$ – RobPratt Jan 21 at 21:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.