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.

Pages: 1 2

9 Responses to “A Prime Number Puzzle”

  1. Paul said

    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)
    
  2. Andras said

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    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))
    }
    
  3. Andras said

    Excuse me for the numbers, hilite.me does not format very well for pp…

  4. Andras said

    And it would be great if we could edit our comments.

  5. Francesco said

    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.

  6. Francesco said
    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

  7. Josef Svenningsson said
    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] ]
    
  8. Mike said

    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:

    ps = "11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97".split()
    
    def primepuzzle(n, m='', ps=ps, hd=[]):
    	if len(m) == n:
    		return int(m)
    
    	if not m:
    		return primepuzzle(n, str(n), ps, hd)
    
    	if ps[0][0] != m[-1]:
    		return primepuzzle(n, m, ps[1:], hd + ps[:1])
    	
    	return primepuzzle(n, m + ps[0][1], hd + ps[1:], [])
    
    for n in range(1,10):
    	print(n, primepuzzle(n))
    
    
  9. Claire said

    @Paul ,@Francesco Can you solve this problem in C++,please? Thank you.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: