Múltiplos repitunos

PorJosé A. Alonso 26-marzo-201825-marzo-2022

El ejercicio 4 de la Olimpiada Matemáticas de 1993 es el siguiente:

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 -> [Integer]

1	multiplosRepitunos :: Integer -> 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,

   head (multiplosRepitunos  7 10)       == 111111
   head (multiplosRepitunos  7 (10^10))  == 111111111111
   head (multiplosRepitunos  7 (10^20))  == 111111111111111111111111
   head (multiplosRepitunos 19 (10^10))  == 111111111111111111

head (multiplosRepitunos 7 10) == 111111

head (multiplosRepitunos 7 (10^10)) == 111111111111

head (multiplosRepitunos 7 (10^20)) == 111111111111111111111111

head (multiplosRepitunos 19 (10^10)) == 111111111111111111

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
import Test.QuickCheck

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

multiplosRepitunos :: Integer -> Integer -> [Integer]
multiplosRepitunos p n =
  [x | x <- dropWhile (<= n) 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 -> [Integer]
multiplosRepitunos2 p n =
  [x | x <- dropWhile (<= n) repitunos2
     , mod x p == 0]

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

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

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

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

import Data.Numbers.Primes

import Test.QuickCheck

-- 1ª solución

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

multiplosRepitunos :: Integer -> Integer -> [Integer]

multiplosRepitunos p n =

[x | x <- dropWhile (<= n) 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 -> [Integer]

multiplosRepitunos2 p n =

[x | x <- dropWhile (<= n) repitunos2

, mod x p == 0]

repitunos2 :: [Integer]

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

-- Comprobación

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

-- La propiedad es

prop_multiplosRepitunos :: Int -> Integer -> Property

prop_multiplosRepitunos k n =

k > 2 && n > 0 ==>

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

-- La comprobación es

-- λ> quickCheck prop_multiplosRepitunos

-- +++ OK, passed 100 tests.

5 Comentarios

import Test.QuickCheck
import Data.Numbers.Primes (isPrime)
listaNumero :: [Integer] -> Integer
listaNumero xs = sum [x*(10^n) | (x,n)<-zip xs [length xs-1,length xs-2..0]]

unos :: [Integer]
unos = [listaNumero (replicate n 1) | n <-[1..]]

multiplosRepitunos :: Integer -> Integer -> [Integer]
multiplosRepitunos p n | p == 2 && p == 5 && not(isPrime p) = error "No es posible con estos valores"
                       | otherwise = [x | x<- dropWhile (<n) unos, x`mod`p==0]

propiedad p n = p > 5 && n > 0 && isPrime p ==> not (null [x | x<-multiplosRepitunos p n, x > n])

import Test.QuickCheck

import Data.Numbers.Primes (isPrime)

listaNumero :: [Integer] -> Integer

listaNumero xs = sum [x*(10^n) | (x,n)<-zip xs [length xs-1,length xs-2..0]]

unos :: [Integer]

unos = [listaNumero (replicate n 1) | n <-[1..]]

multiplosRepitunos :: Integer -> Integer -> [Integer]

multiplosRepitunos p n | p == 2 && p == 5 && not(isPrime p) = error "No es posible con estos valores"

| otherwise = [x | x<- dropWhile (<n) unos, x`mod`p==0]

propiedad p n = p > 5 && n > 0 && isPrime p ==> not (null [x | x<-multiplosRepitunos p n, x > n])

Responder

He interpretado, por los ejemplos, que (multiplosRepitunos p n) es la lista de múltiplos repitunos de p mayores que n.

import Test.QuickCheck
import Data.Numbers.Primes (primes)

multiplosRepitunos :: Integer -> Integer -> [Integer]
multiplosRepitunos p n = filter (>n) [read x | m <- [1..],
                                      let x = replicate (m*(p'-1)) '1']
  where p' = fromInteger p

prop_repitunos :: Integer -> Integer -> Property
prop_repitunos m n = n>0 && m>3 ==> (not.null) (multiplosRepitunos p n)
  where p = primes!!(fromInteger m)

import Test.QuickCheck

import Data.Numbers.Primes (primes)

multiplosRepitunos :: Integer -> Integer -> [Integer]

multiplosRepitunos p n = filter (>n) [read x | m <- [1..],

let x = replicate (m*(p'-1)) '1']

where p' = fromInteger p

prop_repitunos :: Integer -> Integer -> Property

prop_repitunos m n = n>0 && m>3 ==> (not.null) (multiplosRepitunos p n)

where p = primes!!(fromInteger m)

Responder

jaibengue dice:

26-marzo-2018 a las 11:23

No es correcta.

Responder

import Data.Numbers.Primes

multiplosRepitunos :: Integer -> Integer -> [Integer]
multiplosRepitunos p n = [x | x <- (dropWhile (<n)[read(replicate x '1') | x <- [1..]]), 
                              mod x p == 0] 
prop_repitunos :: Integer -> Integer -> Property
prop_repitunos p n = p > 3 && isPrime p && n > 0 ==> 
                                         (not.null) (multiplosRepitunos p n)

import Data.Numbers.Primes

multiplosRepitunos :: Integer -> Integer -> [Integer]

multiplosRepitunos p n = [x | x <- (dropWhile (<n)[read(replicate x '1') | x <- [1..]]),

mod x p == 0]

prop_repitunos :: Integer -> Integer -> Property

prop_repitunos p n = p > 3 && isPrime p && n > 0 ==>

(not.null) (multiplosRepitunos p n)

Responder

import Data.List           (genericIndex)
import Test.QuickCheck
import Data.Numbers.Primes (primes)

multiplosRepitunos :: Integer -> Integer -> [Integer]
multiplosRepitunos p n =
  filter (> n) [(10^j-1)`div`9 | j <- [m,m+m..]]
  where m = head [i | i <- [1..], (10^i-1) `mod` (9*p) == 0]

-- Propiedad
-- =========

-- La propiedad es
propRepitunos :: (Positive Integer) -> (Positive Integer) -> Bool
propRepitunos (Positive p) (Positive n) =
  not (null (multiplosRepitunos q n))
  where q = (drop 3 primes) `genericIndex` p

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

import Data.List (genericIndex)

import Test.QuickCheck

import Data.Numbers.Primes (primes)

multiplosRepitunos :: Integer -> Integer -> [Integer]

multiplosRepitunos p n =

filter (> n) [(10^j-1)`div`9 | j <- [m,m+m..]]

where m = head [i | i <- [1..], (10^i-1) `mod` (9*p) == 0]

-- Propiedad

-- =========

-- La propiedad es

propRepitunos :: (Positive Integer) -> (Positive Integer) -> Bool

propRepitunos (Positive p) (Positive n) =

not (null (multiplosRepitunos q n))

where q = (drop 3 primes) `genericIndex` p

-- La comprobación es

-- λ> quickCheck propRepitunos

-- +++ OK, passed 100 tests.

Responder

Múltiplos repitunos

Soluciones

5 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

5 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico