Ir al contenido principal

Números polidivisibles

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.

Definir las funciones

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

tales que

  • polidivisible es la sucesión cuyos elementos son los números polidivisibles. Por ejemplo,
λ> take 20 polidivisibles
[1,2,3,4,5,6,7,8,9,10,12,14,16,18,20,22,24,26,28,30]
λ> 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,
λ> 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
--    λ> all conjetura [1..5]
--    True