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.

Posted by programmingpraxis

Filed in Exercises

9 Comments »

9 Responses to “A Prime Number Puzzle”

Paul said

November 28, 2014 at 9:36 AM

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)

Andras said

November 28, 2014 at 11:51 AM

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))
}

Andras said
November 28, 2014 at 11:53 AM
Excuse me for the numbers, hilite.me does not format very well for pp…
Andras said
November 28, 2014 at 12:13 PM
And it would be great if we could edit our comments.

Francesco said

November 28, 2014 at 3:09 PM

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.

Francesco said

November 28, 2014 at 3:10 PM

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

Josef Svenningsson said

November 30, 2014 at 9:49 PM

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] ]

Mike said

December 1, 2014 at 3:46 AM

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))

Claire said
December 24, 2014 at 8:54 AM
@Paul ,@Francesco Can you solve this problem in C++,please? Thank you.

Programming Praxis