## A Prime Number Puzzle

### November 28, 2014

Today’s exercise comes from the world of recreational mathematics.

For each number

nfrom 1 to 9 inclusive, find a numbermthat begins with the digitn, hasndigits, has each two-digit sequence withinma 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.

Advertisements

Pages: 1 2

In Python. Can be easily solved with greed.

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.

Once again, wrong format :s

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.