abril 2021 – Página 4

Raíces digitales de los números de Fermat.

PorJosé A. Alonso 9-abril-202116-abril-2021

Los números de Fermat son los número de la forma F(n) = 2^(2^n) + 1, donde n es un número natural.

Definir la función

   raizDigitalFermat :: Integer -> Integer

1	raizDigitalFermat :: Integer -> Integer

tal que (raizDigitalFermat n) es la raíz digital del n-ésimo número de Fermat. Por ejemplo,

   raizDigitalFermat 3          ==  5
   raizDigitalFermat (10^2021)  ==  8

1 2	raizDigitalFermat 3 == 5 raizDigitalFermat (10^2021) == 8

Soluciones

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

raizDigitalFermat :: Integer -> Integer
raizDigitalFermat =
  raizDigital . fermat

-- (fermat k) es el k-ésimo número de Fermat. Por ejemplo,
--    fermat 0  ==  3
--    fermat 1  ==  5
--    fermat 2  ==  17
--    fermat 3  ==  257
--    fermat 4  ==  65537
--    fermat 5  ==  4294967297
fermat :: Integer -> Integer
fermat k = 1 + 2^(2^k)

-- (raizDigital n) es la raíz digital de n. Por ejemplo,
--    raizDigital 23451  ==  6
raizDigital :: Integer -> Integer
raizDigital n = 1 + (n-1) `mod` 9

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

-- En el cálculo
--    λ> map raizDigitalFermat [0..20]
--    [3,5,8,5,8,5,8,5,8,5,8,5,8,5,8,5,8,5,8,5,8]
-- se observa que se compone del 3 seguido por la repetición periódica
-- de 5 y 8.

raizDigitalFermat2 :: Integer -> Integer
raizDigitalFermat2 0 = 3
raizDigitalFermat2 n
  | odd n     = 5
  | otherwise = 8

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

-- La comparación es
--    λ> raizDigitalFermat 30
--    8
--    (6.76 secs, 536,981,128 bytes)
--    λ> raizDigitalFermat2 30
--    8
--    (0.01 secs, 98,400 bytes)

-- 1ª solución

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

raizDigitalFermat :: Integer -> Integer

raizDigitalFermat =

raizDigital . fermat

-- (fermat k) es el k-ésimo número de Fermat. Por ejemplo,

-- fermat 0 == 3

-- fermat 1 == 5

-- fermat 2 == 17

-- fermat 3 == 257

-- fermat 4 == 65537

-- fermat 5 == 4294967297

fermat :: Integer -> Integer

fermat k = 1 + 2^(2^k)

-- (raizDigital n) es la raíz digital de n. Por ejemplo,

-- raizDigital 23451 == 6

raizDigital :: Integer -> Integer

raizDigital n = 1 + (n-1) `mod` 9

-- 2ª solución

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

-- En el cálculo

-- λ> map raizDigitalFermat [0..20]

-- [3,5,8,5,8,5,8,5,8,5,8,5,8,5,8,5,8,5,8,5,8]

-- se observa que se compone del 3 seguido por la repetición periódica

-- de 5 y 8.

raizDigitalFermat2 :: Integer -> Integer

raizDigitalFermat2 0 = 3

raizDigitalFermat2 n

| odd n = 5

| otherwise = 8

-- Comparación de eficiencia

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

-- La comparación es

-- λ> raizDigitalFermat 30

-- 8

-- (6.76 secs, 536,981,128 bytes)

-- λ> raizDigitalFermat2 30

-- 8

-- (0.01 secs, 98,400 bytes)

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>

Persistencia aditiva

PorJosé A. Alonso 8-abril-202115-abril-2021

La raíz digital de un número entero positivo n es el dígito resulta al sumar sus dígitos, volviendo a sumar reiteradamente los resultados de esa suma y de las siguientes hasta que la suma sea un número de un dígito, al que se llama la raíz digital del número n y se representa pod D(n). Por ejemplo, la raíz digital del número 23451 es 6, porque 2+3+4+5+1 = 15 y sumando los dígitos del 15 resulta 6.

La persistencia aditiva de un número entero positivo es el número de veces que hay sumar sus dígitos para llegar a su raíz digital. Por ejemplo, la persistencia aditiva de 2718 es 2: primero encontramos que 2+7+1+8 = 18, luego que 1+8 = 9.

Definir la función

   persistencia :: Integer -> Integer

1	persistencia :: Integer -> Integer

tal que (persistencia n) es la persistencia del número entero positivo n. Por ejemplo,

   persistencia 2718                     ==  2
   persistencia 199                      ==  3
   persistencia 19999999999999999999999  ==  4

persistencia 2718 == 2

persistencia 199 == 3

persistencia 19999999999999999999999 == 4

Soluciones

import Data.List (genericLength)
import Test.QuickCheck (Property, (==>), quickCheck)

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

persistencia :: Integer -> Integer
persistencia n
  | n < 10    = 0
  | otherwise = 1 + persistencia (sumaDigitos n)

-- (sumaDigitos n) es la suma de los dígitos de n. Por ejemplo,
--    sumaDigitos 2021  ==  5
sumaDigitos :: Integer -> Integer
sumaDigitos = sum . digitos

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

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

persistencia2 :: Integer -> Integer
persistencia2 = aux 0
  where aux m n
          | n < 10    = m
          | otherwise = aux (m+1) (sumaDigitos n)

-- 3ª solución
-- ===========

persistencia3 :: Integer -> Integer
persistencia3 n =
  genericLength (takeWhile (>9) (iterate sumaDigitos n))

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_equiv :: Integer -> Property
prop_equiv n =
  n > 0 ==>
  all (== (persistencia n))
      [persistencia2 n,
       persistencia3 n]

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

import Data.List (genericLength)

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

-- 1ª solución

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

persistencia :: Integer -> Integer

persistencia n

| n < 10 = 0

| otherwise = 1 + persistencia (sumaDigitos n)

-- (sumaDigitos n) es la suma de los dígitos de n. Por ejemplo,

-- sumaDigitos 2021 == 5

sumaDigitos :: Integer -> Integer

sumaDigitos = sum . digitos

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

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

digitos :: Integer -> [Integer]

digitos x = [read [c] | c <- show x]

-- 2ª solución

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

persistencia2 :: Integer -> Integer

persistencia2 = aux 0

where aux m n

| n < 10 = m

| otherwise = aux (m+1) (sumaDigitos n)

-- 3ª solución

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

persistencia3 :: Integer -> Integer

persistencia3 n =

genericLength (takeWhile (>9) (iterate sumaDigitos n))

-- Comprobación de equivalencia

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

-- La propiedad es

prop_equiv :: Integer -> Property

prop_equiv n =

n > 0 ==>

all (== (persistencia n))

[persistencia2 n,

persistencia3 n]

-- La comprobación es

-- λ> quickCheck prop_equiv

-- +++ 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>

Raíces digitales de potencias de dos

PorJosé A. Alonso 7-abril-202114-abril-2021

La raíz digital de un número entero positivo n es el dígito resulta al sumar sus dígitos, volviendo a sumar reiteradamente los resultados de esa suma y de las siguientes hasta que la suma sea un número de un dígito, al que se llama la raíz digital del número n y se representa por D(n). Por ejemplo, la raíz digital del número 23451 es 6, porque 2+3+4+5+1 = 15 y sumando los dígitos del 15 resulta 6.

Definir la función

   raizDigitalPotencia :: Integer -> Integer

1	raizDigitalPotencia :: Integer -> Integer

tal que (raizDigitalPotencia n) es la raíz digital de 2^n. Por ejemplo,

   raizDigitalPotencia 6            ==  1
   raizDigitalPotencia (10^(10^8))  ==  7

1 2	raizDigitalPotencia 6 == 1 raizDigitalPotencia (10^(10^8)) == 7

Soluciones

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

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

raizDigitalPotencia :: Integer -> Integer
raizDigitalPotencia n =
  raizDigital (2^n)

-- (raizDigital n) es la raíz digital de n. Por ejemplo,
--    raizDigital 23451  ==  6
raizDigital :: Integer -> Integer
raizDigital n = 1 + (n-1) `mod` 9

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

-- Calculando las raíces digitales de los primeros números se obtiene
--    λ> map raizDigitalPotencia [0..29]
--    [1,2,4,8,7,5,1,2,4,8,7,5,1,2,4,8,7,5,1,2,4,8,7,5,1,2,4,8,7,5]
-- Se observa se repite el período 1,2,4,8,7,5.

raizDigitalPotencia2 :: Integer -> Integer
raizDigitalPotencia2 n
    | m == 0 = 1
    | m == 1 = 2
    | m == 2 = 4
    | m == 3 = 8
    | m == 4 = 7
    | m == 5 = 5
  where m = n `mod` 6

-- 3ª solución
-- ===========

raizDigitalPotencia3 :: Integer -> Integer
raizDigitalPotencia3 n =
  case (n `mod` 6) of
    0 -> 1
    1 -> 2
    2 -> 4
    3 -> 8
    4 -> 7
    5 -> 5

-- 4ª solución
-- ===========

raizDigitalPotencia4 :: Integer -> Integer
raizDigitalPotencia4 n =
  raizDigital (2^(mod n 6))

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_raizDigitalPotencia :: Integer -> Property
prop_raizDigitalPotencia n =
  n >= 0 ==>
  all (== (raizDigitalPotencia n))
      [raizDigitalPotencia2 n,
       raizDigitalPotencia3 n,
       raizDigitalPotencia4 n]

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

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

-- La comparación es
--    λ> raizDigitalPotencia 300000000
--    1
--    (2.82 secs, 149,107,152 bytes)
--    λ> raizDigitalPotencia2 300000000
--    1
--    (0.01 secs, 98,480 bytes)
--    λ> raizDigitalPotencia3 300000000
--    1
--    (0.01 secs, 98,440 bytes)
--    λ> raizDigitalPotencia4 300000000
--    1
--    (0.01 secs, 98,568 bytes)
--
--    λ> raizDigitalPotencia2 (10^(10^8))
--    7
--    (3.09 secs, 123,233,992 bytes)
--    λ> raizDigitalPotencia3 (10^(10^8))
--    7
--    (3.07 secs, 123,232,728 bytes)
--    λ> raizDigitalPotencia4 (10^(10^8))
--    7
--    (3.18 secs, 123,234,344 bytes)

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

-- 1ª solución

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

raizDigitalPotencia :: Integer -> Integer

raizDigitalPotencia n =

raizDigital (2^n)

-- (raizDigital n) es la raíz digital de n. Por ejemplo,

-- raizDigital 23451 == 6

raizDigital :: Integer -> Integer

raizDigital n = 1 + (n-1) `mod` 9

-- 2ª solución

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

-- Calculando las raíces digitales de los primeros números se obtiene

-- λ> map raizDigitalPotencia [0..29]

-- [1,2,4,8,7,5,1,2,4,8,7,5,1,2,4,8,7,5,1,2,4,8,7,5,1,2,4,8,7,5]

-- Se observa se repite el período 1,2,4,8,7,5.

raizDigitalPotencia2 :: Integer -> Integer

raizDigitalPotencia2 n

| m == 0 = 1

| m == 1 = 2

| m == 2 = 4

| m == 3 = 8

| m == 4 = 7

| m == 5 = 5

where m = n `mod` 6

-- 3ª solución

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

raizDigitalPotencia3 :: Integer -> Integer

raizDigitalPotencia3 n =

case (n `mod` 6) of

0 -> 1

1 -> 2

2 -> 4

3 -> 8

4 -> 7

5 -> 5

-- 4ª solución

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

raizDigitalPotencia4 :: Integer -> Integer

raizDigitalPotencia4 n =

raizDigital (2^(mod n 6))

-- Comprobación de equivalencia

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

-- La propiedad es

prop_raizDigitalPotencia :: Integer -> Property

prop_raizDigitalPotencia n =

n >= 0 ==>

all (== (raizDigitalPotencia n))

[raizDigitalPotencia2 n,

raizDigitalPotencia3 n,

raizDigitalPotencia4 n]

-- La comprobación es

-- λ> quickCheck prop_raizDigitalPotencia

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> raizDigitalPotencia 300000000

-- 1

-- (2.82 secs, 149,107,152 bytes)

-- λ> raizDigitalPotencia2 300000000

-- 1

-- (0.01 secs, 98,480 bytes)

-- λ> raizDigitalPotencia3 300000000

-- 1

-- (0.01 secs, 98,440 bytes)

-- λ> raizDigitalPotencia4 300000000

-- 1

-- (0.01 secs, 98,568 bytes)

-- λ> raizDigitalPotencia2 (10^(10^8))

-- 7

-- (3.09 secs, 123,233,992 bytes)

-- λ> raizDigitalPotencia3 (10^(10^8))

-- 7

-- (3.07 secs, 123,232,728 bytes)

-- λ> raizDigitalPotencia4 (10^(10^8))

-- 7

-- (3.18 secs, 123,234,344 bytes)

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>

Raíz digital

PorJosé A. Alonso 6-abril-202113-abril-2021

La raíz digital de un número entero positivo n es el dígito que resulta al sumar sus dígitos, volviendo a sumar reiteradamente los resultados de esa suma y de las siguientes hasta que la suma sea un número de un dígito, al que se llama la raíz digital del número n y se representa por D(n). Por ejemplo, la raíz digital del número 23451 es 6, porque 2+3+4+5+1 = 15 y sumando los dígitos del 15 resulta 6.

Definir la función

   raizDigital :: Integer -> Integer

1	raizDigital :: Integer -> Integer

tal que (raizDigital n) es la raíz digital del entero positivo n. Por ejemplo,

   raizDigital 23451  ==  6

1	raizDigital 23451 == 6

Comprobar con QuickCheck las siguientes propiedades de la raíz digital:

D(m + n) = D(D(m) + D(n)).
D(mn) = D(D(m)D(n)).
D(m^n) = D(D(m)^n).
D(D(n)) = D(n).
D(n + 9) = D(n).
D(9n) = 9.

Soluciones

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

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

raizDigital :: Integer -> Integer
raizDigital n
  | n < 10    = n
  | otherwise = raizDigital (sumaDigitos n)

-- (sumaDigitos n) es la suma de los dígitos de n. Por ejemplo,
--    sumaDigitos 2021  ==  5
sumaDigitos :: Integer -> Integer
sumaDigitos = sum . digitos

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

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

raizDigital2 :: Integer -> Integer
raizDigital2 n =
  head (dropWhile (>9) (iterate sumaDigitos n))

-- 3ª solución
-- ===========

raizDigital3 :: Integer -> Integer
raizDigital3 n
  | m == 0    = 9
  | otherwise = m
  where m = n `mod` 9

-- 4ª solución
-- ===========

raizDigital4 :: Integer -> Integer
raizDigital4 n = 1 + (n-1) `mod` 9

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_raizDigital_equiv :: Integer -> Property
prop_raizDigital_equiv n =
  n > 0 ==>
  all (== (raizDigital n))
      [raizDigital2 n,
       raizDigital3 n,
       raizDigital4 n]

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

-- Propiedades
-- ===========

-- Las propiedades son
prop_raizDigital :: Integer -> Integer -> Property
prop_raizDigital m n =
  m > 0 && n > 0 ==>
  d(m + n) == d(d(m) + d(n)) &&
  d(m*n) == d(d(m)*d(n)) &&
  d(m^n) == d(d(m)^n) &&
  d(d(n)) == d(n) &&
  d(n + 9) == d(n) &&
  d(9*n) == 9
  where d = raizDigital

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

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

-- 1ª solución

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

raizDigital :: Integer -> Integer

raizDigital n

| n < 10 = n

| otherwise = raizDigital (sumaDigitos n)

-- (sumaDigitos n) es la suma de los dígitos de n. Por ejemplo,

-- sumaDigitos 2021 == 5

sumaDigitos :: Integer -> Integer

sumaDigitos = sum . digitos

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

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

digitos :: Integer -> [Integer]

digitos x = [read [c] | c <- show x]

-- 2ª solución

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

raizDigital2 :: Integer -> Integer

raizDigital2 n =

head (dropWhile (>9) (iterate sumaDigitos n))

-- 3ª solución

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

raizDigital3 :: Integer -> Integer

raizDigital3 n

| m == 0 = 9

| otherwise = m

where m = n `mod` 9

-- 4ª solución

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

raizDigital4 :: Integer -> Integer

raizDigital4 n = 1 + (n-1) `mod` 9

-- Comprobación de equivalencia

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

-- La propiedad es

prop_raizDigital_equiv :: Integer -> Property

prop_raizDigital_equiv n =

n > 0 ==>

all (== (raizDigital n))

[raizDigital2 n,

raizDigital3 n,

raizDigital4 n]

-- La comprobación es

-- λ> quickCheck prop_raizDigital_equiv

-- +++ OK, passed 100 tests.

-- Propiedades

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

-- Las propiedades son

prop_raizDigital :: Integer -> Integer -> Property

prop_raizDigital m n =

m > 0 && n > 0 ==>

d(m + n) == d(d(m) + d(n)) &&

d(m*n) == d(d(m)*d(n)) &&

d(m^n) == d(d(m)^n) &&

d(d(n)) == d(n) &&

d(n + 9) == d(n) &&

d(9*n) == 9

where d = raizDigital

-- La comprobación es

-- λ> quickCheck prop_raizDigital

-- +++ 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>

Antiimágenes de funciones crecientes bidimensionales

PorJosé A. Alonso 5-abril-202129-marzo-2021

Una función f de pares de números naturales en números naturales es estrictamente creciente en ambos argumentos si

para x1 < x2, se tiene f(x1,y) < f(x1,y), para todo y y
para y1 < y2, se tiene f(x,y1) < f(x,y2), para todo x.

Por ejemplo, la función f definida por f(x,y) = x^2+3^y es creciente en ambos argumentos.

Las antiimágenes por f de t son los pares (x,y) tales que f(x,y) = t. Por ejemplo, las antimágenes por f(x,y) = x^2+3^y de 82 son los pares (1,4) y (9,0).

Definir la función

   antiimagenes :: Integral a => ((a,a) -> a) -> a -> [(a,a)]

1	antiimagenes :: Integral a => ((a,a) -> a) -> a -> [(a,a)]

tal que (antiimagenes f t) es la lista de las antiimágenes por f de t, donde se supone que f es una función de pares de números naturales en números naturales que es estrictamente creciente en ambos argumentos. Por ejemplo,

   antiimagenes (\(x,y) -> x^2+3^y) 82        ==  [(1,4),(9,0)]
   antiimagenes (\(x,y) -> x^2+3^y) 387421785 ==  [(36,18)]

1 2	antiimagenes (\(x,y) -> x^2+3^y) 82 == [(1,4),(9,0)] antiimagenes (\(x,y) -> x^2+3^y) 387421785 == [(36,18)]

Soluciones

[schedule expon=’2021-04-12′ expat=»06:00″]

Las soluciones se pueden escribir en los comentarios hasta el 12 de abril.
El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>

[/schedule]

[schedule on=’2021-04-12′ at=»06:00″]

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

antiimagenes :: Integral a => ((a,a) -> a) -> a -> [(a,a)]
antiimagenes f t =
  [(x,y) | x <- [0..t], y <- [0..t ], f (x,y) == t]

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

antiimagenes2 :: Integral a => ((a,a) -> a) -> a -> [(a,a)]
antiimagenes2 f t = antiimagenesEn (0,t)
  where antiimagenesEn (a,b) = [(x,y) | x <- [a..t], y <- [b,b-1..0], f (x,y) == t]

-- 3ª solución
-- ===========

antiimagenes3 :: Integral a => ((a,a) -> a) -> a -> [(a,a)]
antiimagenes3 f t = antiimagenesEn (0,t)
  where antiimagenesEn (a,b)
          | a > t || b < 0 = []
          | c < t          = antiimagenesEn (a+1,b)
          | c == t         = (a,b) : antiimagenesEn (a+1,b-1)
          | c > t          = antiimagenesEn (a,b-1)
          where c = f (a,b)

-- 3ª solución
-- ===========

antiimagenes4 :: Integral a => ((a,a) -> a) -> a -> [(a,a)]
antiimagenes4 f t = desde (0,p) (q,0) where
  p = menor (-1,t) (\ y -> f (0,y)) t
  q = menor (-1,t) (\ x -> f (x,0)) t
  desde (x1,y1) (x2,y2)
    | x2 < x1 || y1 < y2 = []
    | y1 - y <= x2 - x1  = fila x
    | otherwise          = columna y
    where
      x = menor (x1-1,x2) (\ x -> f (x,r)) t
      y = menor (y2-1,y1) (\ y -> f (c,y)) t
      c = (x1 + x2) `div` 2
      r = (y1 + y2) `div` 2
      fila x
        | z < t  = desde (x1,y1) (x2,r+1)
        | z == t = (x,r) : desde (x1,y1) (x-1,r+1) ++ desde (x+1,r-1) (x2,y2)
        | z > t  = desde (x1,y1) (x-1,r+1) ++ desde (x,r-1) (x2,y2)
        where z = f (x,r)
      columna y
        | z < t  = desde (c+1,y1) (x2,y2)
        | z == t = (c,y) : desde (x1,y1) (c-1,y+1) ++ desde (c+1,y-1) (x2,y2)
        | z > t  = desde (x1,y1) (c-1,y) ++ desde (c+1,y-1) (x2,y2)
        where z = f (c, y)


-- (menor (a,b) f t), suponiendo que t <= f b, es el menor x enel
-- intervalo (a,b] tal que t <= f x.
menor :: Integral a => (a,a) -> (a -> a) -> a -> a
menor (a,b) f t
  | a + 1 == b = b
  | t <= f m   = menor (a, m) f t
  | otherwise  = menor (m, b) f t
  where m = (a + b) `div` 2

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

-- La comparación es
--    λ> antiimagenes (\(x,y) -> x^2+3^y) 2383
--    [(14,7)]
--    (15.63 secs, 26,904,500,208 bytes)
--    λ> antiimagenes2 (\(x,y) -> x^2+3^y) 2383
--    [(14,7)]
--    (16.37 secs, 26,950,312,440 bytes)
--    λ> antiimagenes3 (\(x,y) -> x^2+3^y) 2383
--    [(14,7)]
--    (0.03 secs, 11,892,160 bytes)
--    λ> antiimagenes4 (\(x,y) -> x^2+3^y) 2383
--    [(14,7)]
--    (0.01 secs, 277,696 bytes)
--
--    λ> antiimagenes3 (\(x,y) -> x^2+3^y) 59449
--    [(20,10)]
--    (3.77 secs, 1,329,803,208 bytes)
--    λ> antiimagenes4 (\(x,y) -> x^2+3^y) 59449
--    [(20,10)]
--    (0.03 secs, 400,400 bytes)

-- 1ª solución

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

antiimagenes :: Integral a => ((a,a) -> a) -> a -> [(a,a)]

antiimagenes f t =

[(x,y) | x <- [0..t], y <- [0..t ], f (x,y) == t]

-- 2ª solución

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

antiimagenes2 :: Integral a => ((a,a) -> a) -> a -> [(a,a)]

antiimagenes2 f t = antiimagenesEn (0,t)

where antiimagenesEn (a,b) = [(x,y) | x <- [a..t], y <- [b,b-1..0], f (x,y) == t]

-- 3ª solución

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

antiimagenes3 :: Integral a => ((a,a) -> a) -> a -> [(a,a)]

antiimagenes3 f t = antiimagenesEn (0,t)

where antiimagenesEn (a,b)

| a > t || b < 0 = []

| c < t = antiimagenesEn (a+1,b)

| c == t = (a,b) : antiimagenesEn (a+1,b-1)

| c > t = antiimagenesEn (a,b-1)

where c = f (a,b)

-- 3ª solución

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

antiimagenes4 :: Integral a => ((a,a) -> a) -> a -> [(a,a)]

antiimagenes4 f t = desde (0,p) (q,0) where

p = menor (-1,t) (\ y -> f (0,y)) t

q = menor (-1,t) (\ x -> f (x,0)) t

desde (x1,y1) (x2,y2)

| x2 < x1 || y1 < y2 = []

| y1 - y <= x2 - x1 = fila x

| otherwise = columna y

where

x = menor (x1-1,x2) (\ x -> f (x,r)) t

y = menor (y2-1,y1) (\ y -> f (c,y)) t

c = (x1 + x2) `div` 2

r = (y1 + y2) `div` 2

fila x

| z < t = desde (x1,y1) (x2,r+1)

| z == t = (x,r) : desde (x1,y1) (x-1,r+1) ++ desde (x+1,r-1) (x2,y2)

| z > t = desde (x1,y1) (x-1,r+1) ++ desde (x,r-1) (x2,y2)

where z = f (x,r)

columna y

| z < t = desde (c+1,y1) (x2,y2)

| z == t = (c,y) : desde (x1,y1) (c-1,y+1) ++ desde (c+1,y-1) (x2,y2)

| z > t = desde (x1,y1) (c-1,y) ++ desde (c+1,y-1) (x2,y2)

where z = f (c, y)

-- (menor (a,b) f t), suponiendo que t <= f b, es el menor x enel

-- intervalo (a,b] tal que t <= f x.

menor :: Integral a => (a,a) -> (a -> a) -> a -> a

menor (a,b) f t

| a + 1 == b = b

| t <= f m = menor (a, m) f t

| otherwise = menor (m, b) f t

where m = (a + b) `div` 2

-- Comparación de eficiencia

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

-- La comparación es

-- λ> antiimagenes (\(x,y) -> x^2+3^y) 2383

-- [(14,7)]

-- (15.63 secs, 26,904,500,208 bytes)

-- λ> antiimagenes2 (\(x,y) -> x^2+3^y) 2383

-- [(14,7)]

-- (16.37 secs, 26,950,312,440 bytes)

-- λ> antiimagenes3 (\(x,y) -> x^2+3^y) 2383

-- [(14,7)]

-- (0.03 secs, 11,892,160 bytes)

-- λ> antiimagenes4 (\(x,y) -> x^2+3^y) 2383

-- [(14,7)]

-- (0.01 secs, 277,696 bytes)

-- λ> antiimagenes3 (\(x,y) -> x^2+3^y) 59449

-- [(20,10)]

-- (3.77 secs, 1,329,803,208 bytes)

-- λ> antiimagenes4 (\(x,y) -> x^2+3^y) 59449

-- [(20,10)]

-- (0.03 secs, 400,400 bytes)

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>

[/schedule]

Meses: abril 2021

Raíces digitales de los números de Fermat.

Soluciones

Nuevas soluciones

Persistencia aditiva

Soluciones

Nuevas soluciones

Raíces digitales de potencias de dos

Soluciones

Nuevas soluciones

Raíz digital

Soluciones

Nuevas soluciones

Antiimágenes de funciones crecientes bidimensionales

Soluciones

Nuevas soluciones

Entradas recientes

Buscar

Correo electrónico