Múltiplos repitunos (OME1993 P4)

PorJosé A. Alonso 5-mayo-202112-mayo-2021

El enunciado del problema 4 de la OME (Olimpiada Matemática Española) del 1993 es

Demostrar que para todo número primo p distinto de 2 y de 5, existen infinitos múltiplos de p de la forma 1111……1 (escrito sólo con unos).

Definir la función

   multiplosRepitunos :: Integer -> [Integer]

1	multiplosRepitunos :: Integer -> [Integer]

tal que (multiplosRepitunos p n) es la lista de los múltiplos repitunos de p (es decir, de la forma 1111…1 escrito sólo con unos), donde p es un número primo distinto de 2 y 5. Por ejemplo,

   take 2 (multiplosRepitunos 7) == [111111,111111111111]
   head (multiplosRepitunos 19)  == 111111111111111111
   length (show (head (multiplosRepitunos (primes !! (10^5))))) == 43324

take 2 (multiplosRepitunos 7) == [111111,111111111111]

head (multiplosRepitunos 19) == 111111111111111111

length (show (head (multiplosRepitunos (primes !! (10^5))))) == 43324

Comprobar con QuickCheck que para todo primo p mayor que 5 y todo número entero positivo n, existe un mútiplo repituno de p mayor que n.

Soluciones

import Data.Numbers.Primes (primes)
import Test.QuickCheck (Property, (==>), quickCheck)

-- 1ª solución
-- ===========

multiplosRepitunos :: Integer -> [Integer]
multiplosRepitunos p =
  [x | x <- repitunos
     , mod x p == 0]

-- repitunos es la lista de los números de la forma 111...1 (escrito sólo con
-- unos). Por ejemplo,
--    take 5 repitunos  ==  [1,11,111,1111,11111]
repitunos :: [Integer]
repitunos = 1 : [10*x+1 | x <- repitunos]

-- 2ª solución
-- ===========

multiplosRepitunos2 :: Integer -> [Integer]
multiplosRepitunos2 p =
  [x | x <- repitunos2
     , mod x p == 0]

repitunos2 :: [Integer]
repitunos2 = [div (10^n-1) 9 | n <- [1..]]

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> length (show (head (multiplosRepitunos (primes !! (10^5)))))
--    43324
--    (0.58 secs, 1,272,561,448 bytes)
--    λ> length (show (head (multiplosRepitunos2 (primes !! (10^5)))))
--    43324
--    (5.50 secs, 2,563,458,656 bytes)

-- Comprobación
-- ============

-- La propiedad es
prop_multiplosRepitunos :: Int -> Property
prop_multiplosRepitunos k =
  k > 2  ==>
  not (null (multiplosRepitunos (primes !! k)))

-- La comprobación es
--    λ> quickCheck prop_multiplosRepitunos
--    +++ OK, passed 100 tests.

import Data.Numbers.Primes (primes)

import Test.QuickCheck (Property, (==>), quickCheck)

-- 1ª solución

-- ===========

multiplosRepitunos :: Integer -> [Integer]

multiplosRepitunos p =

[x | x <- repitunos

, mod x p == 0]

-- repitunos es la lista de los números de la forma 111...1 (escrito sólo con

-- unos). Por ejemplo,

-- take 5 repitunos == [1,11,111,1111,11111]

repitunos :: [Integer]

repitunos = 1 : [10*x+1 | x <- repitunos]

-- 2ª solución

-- ===========

multiplosRepitunos2 :: Integer -> [Integer]

multiplosRepitunos2 p =

[x | x <- repitunos2

, mod x p == 0]

repitunos2 :: [Integer]

repitunos2 = [div (10^n-1) 9 | n <- [1..]]

-- Comparación de eficiencia

-- =========================

-- La comparación es

-- λ> length (show (head (multiplosRepitunos (primes !! (10^5)))))

-- 43324

-- (0.58 secs, 1,272,561,448 bytes)

-- λ> length (show (head (multiplosRepitunos2 (primes !! (10^5)))))

-- 43324

-- (5.50 secs, 2,563,458,656 bytes)

-- Comprobación

-- ============

-- La propiedad es

prop_multiplosRepitunos :: Int -> Property

prop_multiplosRepitunos k =

k > 2 ==>

not (null (multiplosRepitunos (primes !! k)))

-- La comprobación es

-- λ> quickCheck prop_multiplosRepitunos

-- +++ OK, passed 100 tests.

Nuevas soluciones

En los comentarios se pueden escribir nuevas soluciones.
El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>

3 Comentarios

import Data.List
import Data.Numbers.Primes

listaNumero :: [Integer] -> Integer
listaNumero [] = 0
listaNumero (x:xs) = x*10^(genericLength (x:xs)-1) + listaNumero xs

multiplosRepitunos :: Integer -> [Integer]
multiplosRepitunos p | not (isPrime p) || p==2 || p==5 = error "el numero introducido no es valido"
                     | otherwise = [listaNumero (genericReplicate k 1) | k<-[listaNumero (replicate n 1)..],
                                    rem (listaNumero (genericReplicate k 1)) p == 0]
                                   where n = genericLength (show p)


prop :: Integer -> Integer -> Property
prop p n = n>0 && (isPrime p) && p>5 ==> head (dropWhile (<=n) (multiplosRepitunos p)) > n

-- quickCheck prop
-- *** Gave up! Passed only 44 tests.
-- (0.01 secs, 18,446,392 bytes)

import Data.List

import Data.Numbers.Primes

listaNumero :: [Integer] -> Integer

listaNumero [] = 0

listaNumero (x:xs) = x*10^(genericLength (x:xs)-1) + listaNumero xs

multiplosRepitunos :: Integer -> [Integer]

multiplosRepitunos p | not (isPrime p) || p==2 || p==5 = error "el numero introducido no es valido"

| otherwise = [listaNumero (genericReplicate k 1) | k<-[listaNumero (replicate n 1)..],

rem (listaNumero (genericReplicate k 1)) p == 0]

where n = genericLength (show p)

prop :: Integer -> Integer -> Property

prop p n = n>0 && (isPrime p) && p>5 ==> head (dropWhile (<=n) (multiplosRepitunos p)) > n

-- quickCheck prop

-- *** Gave up! Passed only 44 tests.

-- (0.01 secs, 18,446,392 bytes)

Responder

-- Definición:
-- ==========

multiplosRepitunos :: Integer -> [Integer]
multiplosRepitunos p = [n | n <- listaUnos, mod n p == 0]

-- listaUnos es una lista de enteros tal que el n-ésimo término es un número
-- formado por n unos. Por ejemplo,
--    λ> take 10 listaUnos
--    [1,11,111,1111,11111,111111,1111111,11111111,111111111,1111111111]

listaUnos :: [Integer]
listaUnos = scanl1 (+) (map (10^) [0..])

-- Propiedad:
-- =========

prop :: Integer -> Integer -> Bool
prop p n = not (isPrime p') || not (null (filter (>n) (multiplosRepitunos p')))
  where p' = abs p + 6

-- La comprobación es:
-- λ> quickCheck prop
-- +++ OK, passed 100 tests.

-- Definición:

-- ==========

multiplosRepitunos :: Integer -> [Integer]

multiplosRepitunos p = [n | n <- listaUnos, mod n p == 0]

-- listaUnos es una lista de enteros tal que el n-ésimo término es un número

-- formado por n unos. Por ejemplo,

-- λ> take 10 listaUnos

-- [1,11,111,1111,11111,111111,1111111,11111111,111111111,1111111111]

listaUnos :: [Integer]

listaUnos = scanl1 (+) (map (10^) [0..])

-- Propiedad:

-- =========

prop :: Integer -> Integer -> Bool

prop p n = not (isPrime p') || not (null (filter (>n) (multiplosRepitunos p')))

where p' = abs p + 6

-- La comprobación es:

-- λ> quickCheck prop

-- +++ OK, passed 100 tests.

Responder

{-

  Sabiendo que el resto de 1111.....11 `div` p == 0

  Podemos "deshacer" la división (algoritmo tradicional antes
  del desastroso método del ABN) y los resíduos se relacionan
  como:

    r{i} = 10 r{i+1} + 1 - p d{i}

  (siendo d{i} el dígito que corresponde en la división al
  resto del paso {i}).

  Además, es obvio que sólo hay un dígito d{i} posible.

  Por tanto todos resíduos "deshaciendo" la división del cole
  son:

-}
reps :: Integer {- prime -} -> [(Integer {- resto -}, Int {- nº de unos -})]
reps p = iterate rec (0, 0)
  where rec (r, s) = head [ (r', s + 1)
                          | d <- [0..9]
                          , let (r', w) = (r + p * d - 1) `divMod` 10
                          , w == 0 ]

-- y los divisores serán aquellos cuyo resto esté formado por unos
multiplosRepitunos :: Integer -> [Integer]
multiplosRepitunos p = [ read (rr ++ take s (repeat '1'))
                       | (r, s) <- reps p
                       , let rr = show r
                       , nub rr == "1"]

{-

*Main> (length . show . head . multiplosRepitunos) (primes!!(10^5))
43324
(0.64 secs, 692,423,320 bytes)

*Main> (length . show . head . multiplosRepitunos) (primes!!(10^6))
7742933
(71.69 secs, 39,323,238,576 bytes)

-}

Sabiendo que el resto de 1111.....11 `div` p == 0

Podemos "deshacer" la división (algoritmo tradicional antes

del desastroso método del ABN) y los resíduos se relacionan

como:

r{i} = 10 r{i+1} + 1 - p d{i}

(siendo d{i} el dígito que corresponde en la división al

resto del paso {i}).

Además, es obvio que sólo hay un dígito d{i} posible.

Por tanto todos resíduos "deshaciendo" la división del cole

son:

reps :: Integer {- prime -} -> [(Integer {- resto -}, Int {- nº de unos -})]

reps p = iterate rec (0, 0)

where rec (r, s) = head [ (r', s + 1)

| d <- [0..9]

, let (r', w) = (r + p * d - 1) `divMod` 10

, w == 0 ]

-- y los divisores serán aquellos cuyo resto esté formado por unos

multiplosRepitunos :: Integer -> [Integer]

multiplosRepitunos p = [ read (rr ++ take s (repeat '1'))

| (r, s) <- reps p

, let rr = show r

, nub rr == "1"]

*Main> (length . show . head . multiplosRepitunos) (primes!!(10^5))

43324

(0.64 secs, 692,423,320 bytes)

*Main> (length . show . head . multiplosRepitunos) (primes!!(10^6))

7742933

(71.69 secs, 39,323,238,576 bytes)

Responder

Múltiplos repitunos (OME1993 P4)

Soluciones

Nuevas soluciones

3 Comentarios

Leave a Reply to Joaquín Infante RodríguezCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Nuevas soluciones

Se puede imprimir o compartir con

3 Comentarios

Leave a Reply to Joaquín Infante RodríguezCancel reply

Entradas recientes

Buscar

Correo electrónico