rem

Números libres de cuadrados

PorJosé A. Alonso 3-noviembre-201725-abril-2021

Un número entero positivo es libre de cuadrados si no es divisible el cuadrado de ningún entero mayor que 1. Por ejemplo, 70 es libre de cuadrado porque sólo es divisible por 1, 2, 5, 7 y 70; en cambio, 40 no es libre de cuadrados porque es divisible por 2^2.

Definir la función

   libreDeCuadrados :: Integer -> Bool

1	libreDeCuadrados :: Integer -> Bool

tal que (libreDeCuadrados x) se verifica si x es libre de cuadrados. Por ejemplo,

   libreDeCuadrados 70                    ==  True
   libreDeCuadrados 40                    ==  False
   libreDeCuadrados 510510                ==  True
   libreDeCuadrados (((10^10)^10)^10)     ==  False

libreDeCuadrados 70 == True

libreDeCuadrados 40 == False

libreDeCuadrados 510510 == True

libreDeCuadrados (((10^10)^10)^10) == False

Otro ejemplo,

   λ> filter (not . libreDeCuadrados) [1..50]
   [4,8,9,12,16,18,20,24,25,27,28,32,36,40,44,45,48,49,50]

1 2	λ> filter (not . libreDeCuadrados) [1..50] [4,8,9,12,16,18,20,24,25,27,28,32,36,40,44,45,48,49,50]

Soluciones

import Data.Numbers.Primes (primeFactors, primes)
import Data.List (nub)
import Test.QuickCheck

import Data.List (genericLength) -- Para OS

-- 1ª definición:
libreDeCuadrados :: Integer -> Bool
libreDeCuadrados x = x == product (divisoresPrimos x)

-- (divisoresPrimos x) es la lista de los divisores primos de x. Por
-- ejemplo,  
--    divisoresPrimos 40  ==  [2,5]
--    divisoresPrimos 70  ==  [2,5,7]
divisoresPrimos :: Integer -> [Integer]
divisoresPrimos x = [n | n <- divisores x, primo n]

-- (divisores n) es la lista de los divisores del número n. Por ejemplo,
--    divisores 30  ==  [1,2,3,5,6,10,15,30]  
divisores :: Integer -> [Integer]
divisores n = [x | x <- [1..n], n `mod` x == 0]

-- (primo n) se verifica si n es primo. Por ejemplo,
--    primo 30  == False
--    primo 31  == True  
primo :: Integer -> Bool
primo n = divisores n == [1, n]

-- 2ª definición
libreDeCuadrados2 :: Integer -> Bool
libreDeCuadrados2 n = 
    null [x | x <- [2..n], rem n (x^2) == 0]

-- 3ª definición
libreDeCuadrados3 :: Integer -> Bool
libreDeCuadrados3 n = 
    null [x | x <- [2..floor (sqrt (fromIntegral n))], 
              rem n (x^2) == 0]

-- 4ª definición
libreDeCuadrados4 :: Integer -> Bool
libreDeCuadrados4 n = 
  xs == nub xs
  where xs = primeFactors n

-- 5ª definición
libreDeCuadrados5 :: Integer -> Bool
libreDeCuadrados5 n = 
  all (\(x,y) -> x /= y) (zip xs (tail xs))
  where xs = primeFactors n

-- Equivalencia de las definiciones
-- ================================

prop_equivalencia :: Integer -> Property
prop_equivalencia n =
  n > 0 ==>
  all (== libreDeCuadrados n)
      [f n | f <- [ libreDeCuadrados2
                  , libreDeCuadrados3
                  , libreDeCuadrados4
                  , libreDeCuadrados5
                  ]]

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

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

--    λ> libreDeCuadrados 510510
--    True
--    (0.76 secs, 89,522,360 bytes)
--    λ> libreDeCuadrados2 510510
--    True
--    (1.78 secs, 371,826,320 bytes)
--    λ> libreDeCuadrados3 510510
--    True
--    (0.01 secs, 0 bytes)
--    λ> libreDeCuadrados4 510510
--    True
--    (0.00 secs, 152,712 bytes)
--
--    λ> filter libreDeCuadrados3 [1..] !! (2*10^4)
--    32906
--    (2.24 secs, 1,812,139,456 bytes)
--    λ> filter libreDeCuadrados4 [1..] !! (2*10^4)
--    32906
--    (0.51 secs, 936,216,664 bytes)
--    λ> filter libreDeCuadrados5 [1..] !! (2*10^4)
--    32906
--    (0.38 secs, 806,833,952 bytes)
--
--    λ> filter libreDeCuadrados4 [1..] !! (10^5)
--    164499
--    (3.28 secs, 7,470,629,888 bytes)
--    λ> filter libreDeCuadrados5 [1..] !! (10^5)
--    164499
--    (2.88 secs, 6,390,072,384 bytes)

100

import Data.Numbers.Primes (primeFactors, primes)

import Data.List (nub)

import Test.QuickCheck

import Data.List (genericLength) -- Para OS

-- 1ª definición:

libreDeCuadrados :: Integer -> Bool

libreDeCuadrados x = x == product (divisoresPrimos x)

-- (divisoresPrimos x) es la lista de los divisores primos de x. Por

-- ejemplo,

-- divisoresPrimos 40 == [2,5]

-- divisoresPrimos 70 == [2,5,7]

divisoresPrimos :: Integer -> [Integer]

divisoresPrimos x = [n | n <- divisores x, primo n]

-- (divisores n) es la lista de los divisores del número n. Por ejemplo,

-- divisores 30 == [1,2,3,5,6,10,15,30]

divisores :: Integer -> [Integer]

divisores n = [x | x <- [1..n], n `mod` x == 0]

-- (primo n) se verifica si n es primo. Por ejemplo,

-- primo 30 == False

-- primo 31 == True

primo :: Integer -> Bool

primo n = divisores n == [1, n]

-- 2ª definición

libreDeCuadrados2 :: Integer -> Bool

libreDeCuadrados2 n =

null [x | x <- [2..n], rem n (x^2) == 0]

-- 3ª definición

libreDeCuadrados3 :: Integer -> Bool

libreDeCuadrados3 n =

null [x | x <- [2..floor (sqrt (fromIntegral n))],

rem n (x^2) == 0]

-- 4ª definición

libreDeCuadrados4 :: Integer -> Bool

libreDeCuadrados4 n =

xs == nub xs

where xs = primeFactors n

-- 5ª definición

libreDeCuadrados5 :: Integer -> Bool

libreDeCuadrados5 n =

all (\(x,y) -> x /= y) (zip xs (tail xs))

where xs = primeFactors n

-- Equivalencia de las definiciones

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

prop_equivalencia :: Integer -> Property

prop_equivalencia n =

n > 0 ==>

all (== libreDeCuadrados n)

[f n | f <- [ libreDeCuadrados2

, libreDeCuadrados3

, libreDeCuadrados4

, libreDeCuadrados5

]]

-- La comprobación es

-- λ> quickCheck prop_equivalencia

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- λ> libreDeCuadrados 510510

-- True

-- (0.76 secs, 89,522,360 bytes)

-- λ> libreDeCuadrados2 510510

-- True

-- (1.78 secs, 371,826,320 bytes)

-- λ> libreDeCuadrados3 510510

-- True

-- (0.01 secs, 0 bytes)

-- λ> libreDeCuadrados4 510510

-- True

-- (0.00 secs, 152,712 bytes)

-- λ> filter libreDeCuadrados3 [1..] !! (2*10^4)

-- 32906

-- (2.24 secs, 1,812,139,456 bytes)

-- λ> filter libreDeCuadrados4 [1..] !! (2*10^4)

-- 32906

-- (0.51 secs, 936,216,664 bytes)

-- λ> filter libreDeCuadrados5 [1..] !! (2*10^4)

-- 32906

-- (0.38 secs, 806,833,952 bytes)

-- λ> filter libreDeCuadrados4 [1..] !! (10^5)

-- 164499

-- (3.28 secs, 7,470,629,888 bytes)

-- λ> filter libreDeCuadrados5 [1..] !! (10^5)

-- 164499

-- (2.88 secs, 6,390,072,384 bytes)

Sucesión de Cantor de números innombrables

PorJosé A. Alonso 3-febrero-201725-abril-2021

Un número es innombrable si es divisible por 7 o alguno de sus dígitos es un 7. Un juego infantil consiste en contar saltándose los números innombrables:

   1 2 3 4 5 6 ( ) 8 9 10 11 12 13 ( ) 15 16 ( ) 18 ...

1	1 2 3 4 5 6 ( ) 8 9 10 11 12 13 ( ) 15 16 ( ) 18 ...

La sucesión de Cantor se obtiene llenando los huecos de la sucesión anterior
como se indica a continuación:

  1 2 3 4 5 6 (1) 8 9 10 11 12 13 (2) 15 16 (3) 18 19 20 (4) 22 23
  24 25 26 (5) (6) 29 30 31 32 33 34 (1) 36 (8) 38 39 40 41  (9) 43
  44 45 46 (10) 48 (11) 50 51 52 53 54 55 (12) (13) 58 59 60 61 62
  (2) 64 65 66 (15) 68 69 (16) (3) (18) (19) (20) (4) (22) (23) (24)
  (25) 80 81 82 83 (26) 85 86 (5) 88 89 90 (6) 92 93 94 95 96 (29)
  (30) 99 100

1 2 3 4 5 6 (1) 8 9 10 11 12 13 (2) 15 16 (3) 18 19 20 (4) 22 23

24 25 26 (5) (6) 29 30 31 32 33 34 (1) 36 (8) 38 39 40 41 (9) 43

44 45 46 (10) 48 (11) 50 51 52 53 54 55 (12) (13) 58 59 60 61 62

(2) 64 65 66 (15) 68 69 (16) (3) (18) (19) (20) (4) (22) (23) (24)

(25) 80 81 82 83 (26) 85 86 (5) 88 89 90 (6) 92 93 94 95 96 (29)

(30) 99 100

Definir la sucesión

   sucCantor :: [Integer]

1	sucCantor :: [Integer]

cuyos elementos son los términos de la sucesión de Cantor. Por ejemplo,

   λ> take 100 sucCantor
   [1,2,3,4,5,6, 1 ,8,9,10,11,12,13, 2, 15,16, 3, 18,19,20, 4,
    22,23,24,25,26, 5 , 6 ,29,30,31,32,33,34, 1 ,36 , 8 ,38,39,
    40,41, 9 ,43,44,45,46, 10 ,48, 11 ,50,51,52,53,54,55 , 12 ,
    13, 58,59,60,61,62, 2 ,64,65,66, 15 ,68,69, 16 , 3 , 18, 19,
    20, 4, 22, 23, 24 ,25 ,80,81,82,83, 26 ,85,86, 5 ,88,89,90,
    6, 92,93,94,95,96, 29, 30 ,99,100]

   λ> sucCantor2 !! (5+10^6)
   544480

   λ> sucCantor2 !! (6+10^6)
   266086

λ> take 100 sucCantor

[1,2,3,4,5,6, 1 ,8,9,10,11,12,13, 2, 15,16, 3, 18,19,20, 4,

22,23,24,25,26, 5 , 6 ,29,30,31,32,33,34, 1 ,36 , 8 ,38,39,

40,41, 9 ,43,44,45,46, 10 ,48, 11 ,50,51,52,53,54,55 , 12 ,

13, 58,59,60,61,62, 2 ,64,65,66, 15 ,68,69, 16 , 3 , 18, 19,

20, 4, 22, 23, 24 ,25 ,80,81,82,83, 26 ,85,86, 5 ,88,89,90,

6, 92,93,94,95,96, 29, 30 ,99,100]

λ> sucCantor2 !! (5+10^6)

544480

λ> sucCantor2 !! (6+10^6)

266086

Soluciones

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

sucCantor1 :: [Integer]
sucCantor1 = map fst $ scanl f (1,0) [2..]
  where f (a,i) x
          | esInnombrable x = (sucCantor1 !! i, i+1)
          | otherwise       = (x,i)


esInnombrable :: Integer -> Bool
esInnombrable x =
  rem x 7 == 0 || '7' `elem` show x

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

sucCantor2 :: [Integer]
sucCantor2 = aux 0 1
  where aux i x
          | esInnombrable x = sucCantor2 !! i : aux (i+1) (x+1)
          | otherwise       = x : aux i (x+1)

-- 1ª solución

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

sucCantor1 :: [Integer]

sucCantor1 = map fst $ scanl f (1,0) [2..]

where f (a,i) x

| esInnombrable x = (sucCantor1 !! i, i+1)

| otherwise = (x,i)

esInnombrable :: Integer -> Bool

esInnombrable x =

rem x 7 == 0 || '7' `elem` show x

-- 2ª solución

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

sucCantor2 :: [Integer]

sucCantor2 = aux 0 1

where aux i x

| esInnombrable x = sucCantor2 !! i : aux (i+1) (x+1)

| otherwise = x : aux i (x+1)

Referencia

Basado en Cantor’s unspeakable numbers de
CodeGolf.

Números de la suerte

PorJosé A. Alonso 16-diciembre-201625-marzo-2022

Un número de la suerte es un número natural que se genera por una criba, similar a la criba de Eratóstenes, como se indica a continuación:

Se comienza con la lista de los números enteros a partir de 1:

   1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25...

1	1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25...

Se eliminan los números de dos en dos

   1,  3,  5,  7,  9,   11,   13,   15,   17,   19,   21,   23,   25...

1	1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25...

Como el segundo número que ha quedado es 3, se eliminan los números
restantes de tres en tres:

   1,  3,      7,  9,         13,   15,         19,   21,         25...

1	1, 3, 7, 9, 13, 15, 19, 21, 25...

Como el tercer número que ha quedado es 7, se eliminan los números restantes de
siete en siete:

   1,  3,      7,  9,         13,   15,               21,         25...

1	1, 3, 7, 9, 13, 15, 21, 25...

Este procedimiento se repite indefinidamente y los supervivientes son
los números de la suerte:

   1,3,7,9,13,15,21,25,31,33,37,43,49,51,63,67,69,73,75,79

1	1,3,7,9,13,15,21,25,31,33,37,43,49,51,63,67,69,73,75,79

Definir la sucesión

   numerosDeLaSuerte :: [Int]

1	numerosDeLaSuerte :: [Int]

cuyos elementos son los números de la suerte. Por ejemplo,

   λ> take 20 numerosDeLaSuerte
   [1,3,7,9,13,15,21,25,31,33,37,43,49,51,63,67,69,73,75,79]
   λ> numerosDeLaSuerte !! 1500
   13995

λ> take 20 numerosDeLaSuerte

[1,3,7,9,13,15,21,25,31,33,37,43,49,51,63,67,69,73,75,79]

λ> numerosDeLaSuerte !! 1500

13995

Soluciones

-- 1ª definición
numerosDeLaSuerte :: [Int]
numerosDeLaSuerte = criba 3 [1,3..]
  where
    criba i (n:s:xs) =
      n : criba (i + 1) (s : [x | (n, x) <- zip [i..] xs
                                , rem n s /= 0])

-- 2ª definición
numerosDeLaSuerte2 :: [Int]
numerosDeLaSuerte2 =  1 : criba 2 [1, 3..]
  where criba k xs = z : criba (k + 1) (aux xs)
          where z = xs !! (k - 1 )
                aux ws = us ++ aux vs
                  where (us, _:vs) = splitAt (z - 1) ws

-- 1ª definición

numerosDeLaSuerte :: [Int]

numerosDeLaSuerte = criba 3 [1,3..]

where

criba i (n:s:xs) =

n : criba (i + 1) (s : [x | (n, x) <- zip [i..] xs

, rem n s /= 0])

-- 2ª definición

numerosDeLaSuerte2 :: [Int]

numerosDeLaSuerte2 = 1 : criba 2 [1, 3..]

where criba k xs = z : criba (k + 1) (aux xs)

where z = xs !! (k - 1 )

aux ws = us ++ aux vs

where (us, _:vs) = splitAt (z - 1) ws

Números de Harshad hereditarios

PorJosé A. Alonso 3-noviembre-201610-noviembre-2016

Un número de Harshad es un entero divisible entre la suma de sus dígitos. Por ejemplo, 201 es un número de Harshad porque es divisible por 3 (la suma de sus dígitos). Cuando se elimina el último dígito de 201 se obtiene 20 que también es un número de Harshad. Cuando se elimina el último dígito de 20 se obtiene 2 que también es un número de Harshad. Los números como el 201 que son de Harshad y que los números obtenidos eliminando sus últimos dígitos siguen siendo de Harshad se llaman números de Harshad hereditarios por la derecha. Definir la función

   numeroHHD :: Int -> Bool

1	numeroHHD :: Int -> Bool

tal que (numeroHHD n) se verifica si n es un número de Harshad hereditario por la derecha. Por ejemplo,

   numeroHHD 201  ==  True
   numeroHHD 140  ==  False
   numeroHHD 1104 ==  False

numeroHHD 201 == True

numeroHHD 140 == False

numeroHHD 1104 == False

Calcular el mayor número de Harshad hereditario por la derecha con tres dígitos.

Soluciones

-- (numeroH n) se verifica si n es un número de Harshad.
--    numeroH 201  ==  True
numeroH :: Int -> Bool
numeroH n = rem n (sum (digitos n)) == 0

-- (digitos n) es la lista de los dígitos de n. Por ejemplo,
--    digitos 201  ==  [2,0,1]
digitos :: Int -> [Int]
digitos n = [read [d] | d <- show n]

numeroHHD :: Int -> Bool 
numeroHHD n | n < 10    = True
            | otherwise = numeroH n && numeroHHD (div n 10) 

-- El cálculo es
--    ghci> head [n | n <- [999,998..100], numeroHHD n]
--    902

-- (numeroH n) se verifica si n es un número de Harshad.

-- numeroH 201 == True

numeroH :: Int -> Bool

numeroH n = rem n (sum (digitos n)) == 0

-- (digitos n) es la lista de los dígitos de n. Por ejemplo,

-- digitos 201 == [2,0,1]

digitos :: Int -> [Int]

digitos n = [read [d] | d <- show n]

numeroHHD :: Int -> Bool

numeroHHD n | n < 10 = True

| otherwise = numeroH n && numeroHHD (div n 10)

-- El cálculo es

-- ghci> head [n | n <- [999,998..100], numeroHHD n]

-- 902

Triángulos geométricos

PorJosé A. Alonso 2-noviembre-20169-noviembre-2016

Un triángulo geométrico es un triángulo de lados enteros, representados por la terna (a,b,c) tal que a ≤ b ≤ c y están en progresión geométrica, es decir, b^2 = a*c. Por ejemplo, un triángulo de lados a = 144, b = 156 y c = 169.

Definir la función

   numeroTG :: Integer -> Int

1	numeroTG :: Integer -> Int

tal que (numeroTG n) es el número de triángulos geométricos de perímetro menor o igual que n. Por ejemplo

    numeroTG 10  == 3
    numeroTG 100 == 42
    numeroTG 200 == 91

numeroTG 10 == 3

numeroTG 100 == 42

numeroTG 200 == 91

Nota: Los triángulos geométricos de perímetro menor o igual que 20 son

   [(1,1,1),(2,2,2),(3,3,3),(4,4,4),(5,5,5),(6,6,6),(4,6,9)]

1	[(1,1,1),(2,2,2),(3,3,3),(4,4,4),(5,5,5),(6,6,6),(4,6,9)]

Se observa que (1,2,4) aunque cumple que 1+2+4 <= 20 y 2^2 = 1*4 no pertenece a la lista ya que 1+2 > 4 y, por tanto, no hay ningún triángulo cuyos lados midan 1, 2 y 4.

Soluciones

-- 1ª definición:
numeroTG :: Integer -> Int
numeroTG n = 
    length [(a,b,c) | c <- [1..n]
                    , b <- [1..c]
                    , a <- [1..b]
                    , a+b > c
                    , a+b+c <= n
                    , b^2 == a*c
                    ]

-- 2ª definición:
numeroTG2 :: Integer -> Int
numeroTG2 n = 
    length [(a,b,c) | c <- [1..n]
                    , b <- [1..c]
                    , b^2 `rem` c == 0
                    , let a = b^2 `div` c
                    , a+b > c
                    , a+b+c <= n
                    ]

-- Comparación de eficiencia:
--    λ> numeroTG 300
--    143
--    (2.40 secs, 1,496,824,720 bytes)
--    λ> numeroTG2 300
--    143
--    (0.05 secs, 40,908,568 bytes)

-- 1ª definición:

numeroTG :: Integer -> Int

numeroTG n =

length [(a,b,c) | c <- [1..n]

, b <- [1..c]

, a <- [1..b]

, a+b > c

, a+b+c <= n

, b^2 == a*c

]

-- 2ª definición:

numeroTG2 :: Integer -> Int

numeroTG2 n =

length [(a,b,c) | c <- [1..n]

, b <- [1..c]

, b^2 `rem` c == 0

, let a = b^2 `div` c

, a+b > c

, a+b+c <= n

]

-- Comparación de eficiencia:

-- λ> numeroTG 300

-- 143

-- (2.40 secs, 1,496,824,720 bytes)

-- λ> numeroTG2 300

-- 143

-- (0.05 secs, 40,908,568 bytes)

Referencia

El ejercicio está basado en el problema 370 del proyecto Euler.

Números libres de cuadrados

Soluciones

Sucesión de Cantor de números innombrables

Soluciones

Referencia

Números de la suerte

Soluciones

Números de Harshad hereditarios

Soluciones

Triángulos geométricos

Soluciones

Referencia

Entradas recientes

Buscar

Correo electrónico