-- ----------------------------------------------------------------------------
-- A Haskell program for http://oeis.org/A059471 :
-- a(1) = 2; a(n+1) is obtained by and trying to change just one digit of a(n), 
-- starting with the least significant digit, until a new prime is reached.
-- ----------------------------------------------------------------------------

import Data.Set (Set, fromList, notMember, insert)
import Data.List (delete, find)
import Data.Numbers.Primes (isPrime)
import OEISaux (bFile')

a059471 n = a059471_list !! (n-1)
a059471_list = [2,3,5] ++ (successorOf 5 $ fromList [2,3,5]) where 

   successorOf :: Integer -> Set Integer -> [Integer]
   successorOf x obtained = 
      case find (\m -> m `notMember` obtained && isPrime m) 
                $ candidates x of
                Nothing -> []
                Just y  -> y : successorOf y (insert y obtained) 

   candidates :: Integer -> [Integer]
   candidates n = map read $ cand ns [] $ cins where

      cand :: String -> String -> [String] -> [String]
      cand []     ys (zs:zss) = map (: ys) zs
      cand (x:xs) ys (zs:zss) = map (\i -> reverse xs ++ [i] ++ ys) zs 
                                ++ cand xs (x:ys) zss 

      cins :: [String]
      cins = (zipWith delete 
              ns $ ["1379"]
                   ++ if null higher
                         then []
                         else replicate (length higher - 1) deci ++ [deci'])
             ++ [deci'] 

      ns :: String
      ns@(low:higher) = reverse $ show n 

      deci, deci' :: String
      deci = "0123456789"
      deci' = tail deci

b059471 :: IO ()
b059471 = bFile' "A059471" a059471_list 1     --        -> b059471.txt (250 KB)
--           4.714 sec, compiled (Glasgow Haskell Compiler), Mac OS X, 2.66 GHz
-- ----------------------------------------------------------------------------
--                                              Reinhard Zumkeller, Apr 20 2011
--                                                 reinhard.zumkeller@gmail.com