Sucesión de cubos perfectos

Definir la lista

   sucesion :: [Integer]

1	sucesion :: [Integer]

cuyos elementos son los términos de la sucesión

   107811/3, 110778111/3, 111077781111/3, 111107777811111/3, ...

1	107811/3, 110778111/3, 111077781111/3, 111107777811111/3, ...

Por ejemplo,

   λ> take 5 sucesion
   [35937,36926037,37025927037,37035925937037,37036925926037037]
   λ> length (show (sucesion2 !! (3*10^6)))
   9000005

λ> take 5 sucesion

[35937,36926037,37025927037,37035925937037,37036925926037037]

λ> length (show (sucesion2 !! (3*10^6)))

9000005

Comprobar con QuickCheck que todos los términos de la sucesión son cubos perfectos.

Soluciones

import Test.QuickCheck

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

sucesion :: [Integer]
sucesion = map termino [1..]

-- (termino n) es el término n-ésimo de la sucesión por ejemplo,
--    termino 1  ==  35937
--    termino 2  ==  36926037
--    termino 3  ==  37025927037
termino :: Int -> Integer
termino n = numerador n `div` 3


-- (numerador n) es el numerador del término n-ésimo de la sucesión por
-- ejemplo,
--    λ> mapM_ print (map numerador [1..5])
--    107811
--    110778111
--    111077781111
--    111107777811111
--    111110777778111111
numerador :: Int -> Integer
numerador n =
  read (replicate n '1' ++ "0" ++ replicate n '7' ++ "81" ++ replicate n '1')

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

-- La propiedad es
prop_sucesion :: Int -> Property
prop_sucesion n =
  n >= 0 ==>
  esCubo (sucesion !! n)

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

-- (esCubo x) se verifica si x es un cubo perfecto. Por ejemplo,
--    esCubo 27  ==  True
--    esCubo 28  ==  False
esCubo :: Integer -> Bool
esCubo x =
  (raizCubicaEntera x)^3 == x

-- (raizCubicaEntera x) es el mayor entero cuyo cubo es menor o igual
-- que x. Por ejemplo,
--    raizCubicaEntera 26  ==  2
--    raizCubicaEntera 27  ==  3
--    raizCubicaEntera 28  ==  3
raizCubicaEntera :: Integer -> Integer
raizCubicaEntera x = aux (1,x)
    where aux (a,b) | d == x    = c
                    | c == a    = c
                    | d < x     = aux (c,b)
                    | otherwise = aux (a,c)
              where c = (a+b) `div` 2
                    d = c^3

-- Otra forma es observando los cubos de los términos de la sucesión
--    λ> map raizCubicaEntera (take 7 sucesion)
--    [33,333,3333,33333,333333,3333333,33333333]

-- La propiedad es
prop_sucesion2 :: Int -> Property
prop_sucesion2 n =
  n >= 0 ==>
  sucesion !! n == ((10^(n+2)-1) `div` 3)^3

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

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

-- Basada en la propiedad anterior.

sucesion2 :: [Integer]
sucesion2 =
  [((10^n-1) `div` 3)^3 | n <- [2..]]

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

-- La propiedad es
prop_equiv :: Int -> Property
prop_equiv n =
  n >= 0 ==>
  sucesion !! n == sucesion2 !! n

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

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

-- La comparación es
--    λ> length (show (sucesion !! (3*10^6)))
--    9000005
--    (6.34 secs, 5,161,177,808 bytes)
--    λ> length (show (sucesion2 !! (3*10^6)))
--    9000005
--    (2.72 secs, 1,124,065,328 bytes)

100

101

102

103

104

105

106

107

108

import Test.QuickCheck

-- 1ª solución

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

sucesion :: [Integer]

sucesion = map termino [1..]

-- (termino n) es el término n-ésimo de la sucesión por ejemplo,

-- termino 1 == 35937

-- termino 2 == 36926037

-- termino 3 == 37025927037

termino :: Int -> Integer

termino n = numerador n `div` 3

-- (numerador n) es el numerador del término n-ésimo de la sucesión por

-- ejemplo,

-- λ> mapM_ print (map numerador [1..5])

-- 107811

-- 110778111

-- 111077781111

-- 111107777811111

-- 111110777778111111

numerador :: Int -> Integer

numerador n =

read (replicate n '1' ++ "0" ++ replicate n '7' ++ "81" ++ replicate n '1')

-- Propiedad

-- =========

-- La propiedad es

prop_sucesion :: Int -> Property

prop_sucesion n =

n >= 0 ==>

esCubo (sucesion !! n)

-- La comprobación es

-- λ> quickCheck prop_sucesion

-- +++ OK, passed 100 tests.

-- (esCubo x) se verifica si x es un cubo perfecto. Por ejemplo,

-- esCubo 27 == True

-- esCubo 28 == False

esCubo :: Integer -> Bool

esCubo x =

(raizCubicaEntera x)^3 == x

-- (raizCubicaEntera x) es el mayor entero cuyo cubo es menor o igual

-- que x. Por ejemplo,

-- raizCubicaEntera 26 == 2

-- raizCubicaEntera 27 == 3

-- raizCubicaEntera 28 == 3

raizCubicaEntera :: Integer -> Integer

raizCubicaEntera x = aux (1,x)

where aux (a,b) | d == x = c

| c == a = c

| d < x = aux (c,b)

| otherwise = aux (a,c)

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

d = c^3

-- Otra forma es observando los cubos de los términos de la sucesión

-- λ> map raizCubicaEntera (take 7 sucesion)

-- [33,333,3333,33333,333333,3333333,33333333]

-- La propiedad es

prop_sucesion2 :: Int -> Property

prop_sucesion2 n =

n >= 0 ==>

sucesion !! n == ((10^(n+2)-1) `div` 3)^3

-- La comprobación es

-- λ> quickCheck prop_sucesion2

-- +++ OK, passed 100 tests.

-- 2ª solución

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

-- Basada en la propiedad anterior.

sucesion2 :: [Integer]

sucesion2 =

[((10^n-1) `div` 3)^3 | n <- [2..]]

-- Comprobación de equivalencia

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

-- La propiedad es

prop_equiv :: Int -> Property

prop_equiv n =

n >= 0 ==>

sucesion !! n == sucesion2 !! n

-- La comprobación es

-- λ> quickCheck prop_equiv

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> length (show (sucesion !! (3*10^6)))

-- 9000005

-- (6.34 secs, 5,161,177,808 bytes)

-- λ> length (show (sucesion2 !! (3*10^6)))

-- 9000005

-- (2.72 secs, 1,124,065,328 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>

Un comentario

import Data.List
listaNumeroC :: [Integer] -> Integer
listaNumeroC xs = sum [x*10^y | (x,y)<- zip xs [y | y<-reverse [0..genericLength xs-1]]]

sucesion’ :: [[Integer]]
sucesion’ = [(replicate k 1)++[1,0]++(replicate (k+1) 7)++[8,1,1]++(replicate k 1) | k<-[0..]]

sucesion :: [Integer]
sucesion = divideTodos (map (listaNumeroC) (sucesion’)) 3

divideTodos :: [Integer] -> Integer -> [Integer]
divideTodos [] n = []
divideTodos (x:xs) n = (div x n) : divideTodos xs n

propCubos :: Bool
propCubos = not (null [k |k<-sucesion, n<-[1..k], k==n^3])

--λ> quickCheck (propCubos)
–-+++ OK, passed 100 tests.
–-(0.02 secs, 76,392 bytes)

import Data.List

listaNumeroC :: [Integer] -> Integer

listaNumeroC xs = sum [x*10^y | (x,y)<- zip xs [y | y<-reverse [0..genericLength xs-1]]]

sucesion’ :: [[Integer]]

sucesion’ = [(replicate k 1)++[1,0]++(replicate (k+1) 7)++[8,1,1]++(replicate k 1) | k<-[0..]]

sucesion = divideTodos (map (listaNumeroC) (sucesion’)) 3

divideTodos :: [Integer] -> Integer -> [Integer]

divideTodos [] n = []

divideTodos (x:xs) n = (div x n) : divideTodos xs n

propCubos :: Bool

propCubos = not (null [k |k<-sucesion, n<-[1..k], k==n^3])

--λ> quickCheck (propCubos)

–-+++ OK, passed 100 tests.

–-(0.02 secs, 76,392 bytes)

Responder

Sucesión de cubos perfectos

Soluciones

Nuevas soluciones

Un comentario

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

Un comentario

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

Entradas recientes

Buscar

Correo electrónico