Menu Close

Números polidivisibles

José A. Alonso,

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
Posted in Medio

7 Comments

  1. jneira
    Responder

    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
      Responder

      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
        Responder

        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
    Responder

    (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
    Responder

    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 Publicar autor
      Responder

      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
      Responder

      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.