What's a more efficient implementation of this puzzle?

Question

The puzzle

For every input number n (n < 10) there is an output number m such that:

• m's first digit is n
• m is an n digit number
• every 2 digit sequence inside m must be a different prime number

The output should be m where m is the smallest number that fulfils the conditions above. If there is no such number, the output should be -1;

Examples

n = 3 -> m = 311

n = 4 -> m = 4113 (note that this is not 4111 as that would be repeating 11)

n = 9 -> m = 971131737

My somewhat working solution

Here's my first stab at this, the "brute force" approach. I am looking for a more elegant solution as this is very inefficient as n grows larger.

public long GetM(int n)
{
    long start = n * (long)Math.Pow((double)10, (double)n - 1);
    long end = n * (long)Math.Pow((double)10, (double)n);
    for (long x = start; x < end; x++)
    {
        long xCopy = x;
        bool allDigitsPrime = true;
        List<int> allPrimeNumbers = new List<int>();
        while (xCopy >= 10)
        {
            long lastDigitsLong = xCopy % 100;
            int lastDigits = (int)lastDigitsLong;
            bool lastDigitsSame = allPrimeNumbers.Count != 0 && allPrimeNumbers.Contains(lastDigits);
            if (!IsPrime(lastDigits) || lastDigitsSame)
            {
                allDigitsPrime = false;
                break;
            }

            xCopy /= 10;
            allPrimeNumbers.Add(lastDigits);
        }

        if (n != 1 && allDigitsPrime)
        {
            return x;
        }
    }

    return -1;
} 

Initial thoughts on how this could be made more efficient

So, clearly the bottleneck here is traversing through the whole list of numbers that could fulfil this condition from n.... to (n+1).... . Instead of simply incrementing the number of every iteration of the loop, there must be some clever way of skipping numbers based on the requirement that the 2 digit sequences must be prime. For instance for n = 5, there is no point going through 50000 - 50999 (50 isn't prime), 51200 - 51299 (12 isn't prime), but I wasn't quite sure how this could be implemented or if it would be enough of an optimization to make the algorithm run for n=9.

Any ideas on this approach or a different optimization approach?

Answer 1

Here's a possible solution, in R, using recursion . It would be interesting to build a tree of all the possible paths

# For every input number n (n < 10) 
# there is an output number m such that:

#  m's first digit is n
#  m is an n digit number
#  every 2 digit sequence inside m must be a different prime number
# Need to select the smallest m that meets the criteria

library('numbers')

mNumHelper <- function(cn,n,pr,cm=NULL)  {
  if (cn == 1) {
    if (n==1) {
      return(1)
    }
    firstDigit <- n
  } else {
    firstDigit <- mod(cm,10)
  }
  possibleNextNumbers <- pr[floor(pr/10) == firstDigit]
  nPossible = length(possibleNextNumbers)
  if (nPossible == 1) {
    nextPrime <- possibleNextNumbers
  } else{
    # nextPrime <- sample(possibleNextNumbers,1)
    nextPrime <- min(possibleNextNumbers)
  }
  pr <- pr[which(pr!=nextPrime)] 
  if (is.null(cm)) {
    cm <- nextPrime
  } else {
    cm = cm * 10 + mod(nextPrime,10)
  }
  cn = cn + 1
  if (cn < n) {
    cm = mNumHelper(cn,n,pr,cm)
  }
  return(cm)
}

mNum <- function(n) {
  pr<-Primes(10,100)
  m <- mNumHelper(1,n,pr)  
}
for (i in seq(1,9)) {
  print(paste('i',i,'m',mNum(i)))
}

Sample output

[1] "i 1 m 1"
[1] "i 2 m 23"
[1] "i 3 m 311"
[1] "i 4 m 4113"
[1] "i 5 m 53113"
[1] "i 6 m 611317"
[1] "i 7 m 7113173"
[1] "i 8 m 83113717"
[1] "i 9 m 971131737"

Solution updated to select the smallest prime from the set of available primes, and remove bad path check since it's not required.

Answer 2

You don't have to try all numbers. You can instead use a different strategy, summed up as "try appending a digit".

Which digit? Well, a digit such that

1. it forms a prime together with your current last digit
2. the prime formed has not occurred in the number before

This should be done recursively (not iteratively), because you may run out of options and then you'd have to backtrack and try a different digit earlier in the number.

This is still an exponential time algorithm, but it avoids most of the search space because it never tries any numbers that don't fit the rule that every pair of adjacent digits must form a prime number.

Answer 3

I just made a list of the two-digit prime numbers, then solved the problem by hand; it took only a few minues. Not every problem requires a computer!