A Prime Number Puzzle
November 28, 2014
First I made a list of all the two-digit primes; I didn’t need a program to do that, but you like you can see a simple program to compute the two-digit primes at http://programmingpraxis.codepad.org/YhAGquhp:
11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
Then I solved the problem by hand. I didn’t count, but there are remarkably few places where there is actually a choice of what digit comes next, and if you work from 1 to 9 it is frequently possible to reuse all or part of a previous solution, so it took only a few minutes to solve the problem, certainly less time than it would take to write a program. Here’s my solution:
1: 1
2: 23
3: 311
4: 4113
5: 53113
6: 611317
7: 7113173
8: 83113717
9: 971131737
The lesson, of course, is that sometimes computers only muck up a simple problem with a complicated solution.
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.