Primos hereditarios
Un número primo es hereditario si todos los números obtenidos eliminando dígitos por la derecha o por la izquierda son primos. Por ejemplo, 3797 es hereditario ya que los números obtenidos eliminando dígitos por la derecha son 3797, 379, 37 y 3 y los obtenidos eliminando dígitos por la izquierda son 3797, 797, 97 y 7 y todos ellos son primos.
Definir la sucesión
1 |
hereditarios :: [Integer] |
cuyos elementos son los números hereditarios. Por ejemplo,
1 2 |
ghci> take 15 hereditarios [2,3,5,7,23,37,53,73,313,317,373,797,3137,3797,739397] |
Soluciones
1 2 3 4 5 6 7 8 9 10 11 12 13 |
import Data.List (inits, tails) import Data.Char (digitToInt) import Data.Numbers.Primes (primes, isPrime) hereditarios :: [Integer] hereditarios = [n | n <- primes, hereditario n] hereditario :: Integer -> Bool hereditario n = all odd (map digitToInt (tail ds)) && all isPrime (map read (tail (inits ds))) && all isPrime (map read (init (tails ds))) where ds = show n |
La búsqueda se puede reducir a los números primos, pues es una condición necesaria para que sea hereditario:
Aunque algo elaborado puede hacerse exponencialmente más rápido que la solución trivial.
Generamos desde la izquierda el árbol con podas hasta la mitad de dígitos.
Generamos desde la derecha el árbol con podas hasta la mitad de dígitos.
Vamos fusionando ambos árboles podando combinaciones que no encajan.
Por A024785, no existirá ningún hereditario de más de 24 dígitos (¿existe alguna cota inferior?).
Así, obtenerlos todos (sin saber que son 15) toma unos 95 mS y tomar los 15 unos 48 mS.