A Prime Number Puzzle
November 28, 2014
Today’s exercise comes from the world of recreational mathematics.
For each number n from 1 to 9 inclusive, find a number m that begins with the digit n, has n digits, has each two-digit sequence within m a different prime number, and is as small as possible.
When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
In Python. Can be easily solved with greed.
from collections import defaultdict primes2 = [11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] P = defaultdict(list) for p in primes2: s = str(p) P[s[0]].append(s) def solve(s): n = int(s) used = set() while len(s) < n: for nextp in P[s[-1]]: if nextp not in used: used.add(nextp) s += nextp[1] break return int(s) for n in "123456789": print n, solve(n)import scala.math._ object PrimePuzzle { def sieve(s: Stream[Int]): Stream[Int] = s.head #:: sieve(s.tail.filter(_ % s.head != 0)) //> sieve: (s: Stream[Int])Stream[Int] val primes = sieve(Stream.from(2)).take(25).toList.map(n => n.toString).filter(s => s.length()==2) //> primes : List[String] = List(11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53 //| , 59, 61, 67, 71, 73, 79, 83, 89, 97) def generatePrimePuzzles(n:Int, s:String, remainingPrimes:List[String]): Stream[String] = { if (n < 2) "does not exist" #:: Stream.empty else if (s.length()==n) Stream(s) else { val nextPrimes = remainingPrimes.filter(p=>p.head == s.last) if(nextPrimes.nonEmpty) generatePrimePuzzles(n, s+nextPrimes.head.tail, remainingPrimes.filterNot(p=>p==nextPrimes.head)) else Stream.empty } } //> generatePrimePuzzles: (n: Int, s: String, remainingPrimes: List[String])Stre //| am[String] for(n <- 1 to 9) yield (n, generatePrimePuzzles(n, n.toString, primes)(0)) //> res0: scala.collection.immutable.IndexedSeq[(Int, String)] = Vector((1,does //| not exist), (2,23), (3,311), (4,4113), (5,53113), (6,611317), (7,7113173), ( //| 8,83113717), (9,971131737)) }Excuse me for the numbers, hilite.me does not format very well for pp…
And it would be great if we could edit our comments.
Haskell:
tenp = ["11","13","17","19","23","29","31","37","41","43","47","53","59", "61","67","71","73","79","83","89","97"] addN :: String -> Int -> [String] -> [String] addN s 0 _ = return s addN s i p = filter ((== last s) . head) p >>= \xc -> addN (s ++ [last xc]) (i-1) (filter (/= xc) p) main = print $ map (\n -> head $ addN (show n) (n-1) tenp) [1..9]I guess using >>= to generate partial permutations would lead to a shorter solution, but after a bit of fiddling I manage to do it.
tenp = ["11","13","17","19","23","29","31","37","41","43","47","53","59", "61","67","71","73","79","83","89","97"] addN :: String -> Int -> [String] -> [String] addN s 0 _ = return s addN s i p = let l = last s in filter ((==l) . head) p >>= \xc -> addN (s ++ [last xc]) (i-1) (filter (/= xc) p) main = print $ map (\n -> head $ addN (show n) (n-1) tenp) [1..9]Once again, wrong format :s
twoDigitPrimes = [11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] puzzle n = minimum $ map mkNumber [ m | nb <- sequence (replicate (n-1) [0..9]) , let m = n:nb , allPairs (`elem` twoDigitPrimes) m ] allPairs p (x:y:xs) = p (mkNumber [x,y]) && allPairs p (y:xs) allPairs p _ = True mkNumber = foldl (\r x -> x + 10*r) 0 main = putStrLn $ unlines $ [ show (puzzle n) | n <- [1..9] ]Once you write down all the 2-digit primes, it is clear that the problem is simple enough to do manually in less time than it would take to write a program. Nevertheless, here’s a recursive Python solution:
@Paul ,@Francesco Can you solve this problem in C++,please? Thank you.