Menu Close

Números polidivisibles

Introducción

Un número natural es polidivisible si cumple las siguientes condiciones:

  • El número formado por sus dos primeros dígitos es divisible por 2.
  • El número formado por sus tres primeros dígitos es divisible por 3.
  • El número formado por sus cuatros primeros dígitos es divisible por 4.
  • etcétera.

Por ejemplo, el número 345654 es un número polidivisible ya que

  • 34 es divisible por 2,
  • 345 es divisible por 3,
  • 3456 es divisible por 4,
  • 34565 es divisible por 5 y
  • 345654 es divisible por 6.

pero 123456 no lo es, porque 1234 no es divisible por 4.

Enunciado

Definir las funciones

  polidivisibles :: [Integer]
  polidivisiblesN :: Integer -> [Integer]

tales que

  • polidivisible es la sucesión cuyos elementos son los números polidivisibles. Por ejemplo,
     ghci> take 20 polidivisibles
     [1,2,3,4,5,6,7,8,9,10,12,14,16,18,20,22,24,26,28,30]
     ghci> take 10 (dropWhile (<=100) polidivisibles)
     [102,105,108,120,123,126,129,141,144,147]
  • (polidivisiblesN k) es la lista de los números polidivisibles con k dígitos. Por ejemplo,
     ghci> polidivisiblesN 2
     [10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44,46,48,
      50,52,54,56,58,60,62,64,66,68,70,72,74,76,78,80,82,84,86,88,
      90,92,94,96,98]

Comprobar que, para n entre 1 y 5, la cantidad de números polidivisibles de n dígitos es 9*10^(n-1)/n!.

Soluciones

polidivisibles :: [Integer]
polidivisibles = [n | n <- [1..], esPolidivisible n]
 
-- (esPolidivisible n) se verifica si n es polidivisible. Por ejemplo, 
--    esPolidivisible 345654  ==  True
--    esPolidivisible 123456  ==  False
esPolidivisible :: Integer -> Bool
esPolidivisible n = 
    and [(n `div` 10^(m-k)) `mod` k == 0 | k <- [2..m]] 
    where m = fromIntegral (length (show n))
 
-- (polidivisiblesN n) es la lista de los números polidivisibles de n
-- dígitos. Por ejemplo, 
--    take 6 (polidivisiblesN 3)  ==  [102,105,108,120,123,126]
--    take 6 (polidivisiblesN 5)  ==  [10200,10205,10240,10245,10280,10285]
polidivisiblesN :: Integer -> [Integer]
polidivisiblesN n = 
    takeWhile (<=10^n-1) (dropWhile (<10^(n-1)) polidivisibles)
 
-- (conjetura k) se verifica si la cantidad de números polidivisibles de
-- k dígitos es 9*10^(k-1)/k!. 
conjetura :: Integer -> Bool
conjetura k = 
    fromIntegral (length (polidivisiblesN k)) == 9*10^(k-1) `div` factorial k
    where factorial n = product [1..n]
 
-- La comprobación de la conjetura para k entre 1 y 5 es
--    ghci> all conjetura [1..5]
--    True

7 soluciones de “Números polidivisibles

  1. jneira

    Nada de show y read por favor :-P

    digits 0 = 0
    digits n = 1 + (digits $ n `div` 10)
     
    esPolidivisible :: Integer -> Bool
    esPolidivisible n = d == 1 || n `mod` d == 0 && nxt
       where d = digits n
             nxt = esPolidivisible $ n `div` 10
     
    polidivisibles :: [Integer]
    polidivisibles = filter esPolidivisible [1..] 
     
    polidivisiblesN :: Integer -> [Integer]
    polidivisiblesN k = takeWhile ((k==).digits) . dropWhile ((k>).digits) $ polidivisibles
    • jneira

      Por supuesto se puede evitar la función digits si usamos polidivisiblesN que ya lo tiene como parámetro.

      esPolidivisible :: Integer -> Bool
      esPolidivisible n = d == 1 || n `mod` d == 0 && nxt
         where d = digits n
               nxt = esPolidivisible $ n `div` 10
       
      polidivisibles :: [Integer]
      polidivisibles = concatMap polidivisiblesN [1..]
       
      polidivisiblesN :: Integer -> [Integer]
      polidivisiblesN k = filter esPolidivisible [10^(k-1)..10^k-1]
      • jneira

        Ya lo siento, estoy espeso hoy, la versión buena sería:

        esPolidivisible :: Integer -> Integer -> Bool
        esPolidivisible d n = d == 1 || n `mod` d == 0 && nxt
           where nxt = esPolidivisible (d-1) $ n `div` 10
         
        polidivisibles :: [Integer]
        polidivisibles = concatMap polidivisiblesN [1..]
         
        polidivisiblesN :: Integer -> [Integer]
        polidivisiblesN k = filter (esPolidivisible k) [10^(k-1)..10^k-1]
  2. josejuan

    (Rápido)

    polidivisiblesN :: Integer -> [Integer]
    polidivisiblesN = (map p [0..] !!) . fromIntegral
     where p 0 = []
           p 1 = [1..9]
           p n = [p | q <- polidivisiblesN (n - 1), d <- [0..9], let p = 10 * q + d, p `mod` n == 0]
     
    polidivisibles :: [Integer]
    polidivisibles = concat $ takeWhile (not.null) $ map polidivisiblesN [1..]
  3. jneira

    También podemos construirlos de forma (co)recursiva, de forma mucho más eficiente que la primera versión:

    polidivisibles2 :: [Integer]
    polidivisibles2 = concatMap polidivisiblesN2 [1..]
     
    polidivisiblesN2 :: Integer -> [Integer]
    polidivisiblesN2 1 = [1..9]
    polidivisiblesN2 k = concatMap f $ polidivisiblesN2 (k-1)
       where f n = [idiv,idiv+k..i+1*10-1]
               where i = n * 10
                     idiv = i + ((k - i `mod` k) `mod` k)

    Medición de tiempos:

    *Sandbox> length $ polidivisiblesN 4
    375
    (0.25 secs, 28477164 bytes)
    *Sandbox> length $ polidivisiblesN2 4
    375
    (0.00 secs, 1034548 bytes)
    *Sandbox> length $ polidivisiblesN 5
    750
    (2.53 secs, 288675112 bytes)
    *Sandbox> length $ polidivisiblesN2 5
    750
    (0.00 secs, 1034612 bytes)
    *Sandbox> length $ polidivisiblesN 6
    1200
    (27.31 secs, 3196761996 bytes)
    *Sandbox> length $ polidivisiblesN2 6
    1200
    (0.02 secs, 1034020 bytes)
    *Sandbox> length $ polidivisiblesN2 25
    1
    (0.06 secs, 15066780 bytes)
    *Sandbox> length $ polidivisiblesN2 26
    0
    (0.08 secs, 15065948 bytes)

    Por tanto, no puede haber números polidivisibles de más de 25 cifras, no?

    • José A. Alonso

      En el artículo de la Wikipedia sobre números polidivisibles, enlazado en el enunciado del ejercicio, se indica que hay un total de 20.456 números polidivisibles el mayor de los cuales es 3608528850368400786036725 que tiene 25 dígitos.

      Con esta definición se calcula rápidamente dicho número

      ghci> polidivisiblesN2 25
      [3608528850368400786036725]
    • jneira

      Otra versión (prometo que la última!) con la misma idea pero usando iterate:

      allPolidivisiblesN :: [[Integer]]
      allPolidivisiblesN = snd <$> iterate f (1,[1..9])
        where f (k,ps) = (k+1, ps >>= g (k+1))
              g k n = [idiv,idiv+k..i+1*10-1]
                where i = n * 10
                      idiv = i + ((k - i `mod` k) `mod` k)
       
      polidivisibles3 :: [Integer]              
      polidivisibles3 = concat allPolidivisiblesN
       
      polidivisiblesN3 :: Integer -> [Integer]
      polidivisiblesN3 k = allPolidivisiblesN !! (fromInteger k-1)

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.