Por 3 o más 5

PorJosé A. Alonso 16-marzo-201720-enero-2019

El enunciado del problema Por 3 o más 5 de ¡Acepta el reto! es el siguiente

Cuenta la leyenda que un famoso matemático, tras aprender a sumar y multiplicar a la tierna edad de 3 años en apenas 5 días, se dio cuenta de que, empezando por 1, podía generar un montón de números sin más que multiplicar por 3 o sumar 5 a alguno de los que ya hubiera generado antes.

Por ejemplo, el 23 (edad a la que se casaría) lo obtuvo así: ((1 + 5) × 3) + 5
Por su parte el 77 (edad a la que tendría su primer bisnieto) lo consiguió: (((1 × 3 + 5) × 3) × 3) + 5

Por mucho que lo intentó, algunos números, sin embargo, resultaron ser imposibles de obtener, como por ejemplo el 5, el 7 o el 15.

Se dice que un número es generable si se puede escribir como una sucesión (quizá vacía) de multiplicaciones por 3 y sumas de 5 al número 1.

Definir las siguientes funciones

   generables     :: [Integer]
   generable      :: Integer -> Bool
   arbolGenerable :: Integer -> Tree Integer

generables :: [Integer]

generable :: Integer -> Bool

arbolGenerable :: Integer -> Tree Integer

tales que

generables es la sucesión de los números generables. Por ejemplo,

     λ> take 20 generables
     [1,3,6,8,9,11,13,14,16,18,19,21,23,24,26,27,28,29,31,32]
     λ> generables !! (10^6)
     1250008

λ> take 20 generables

[1,3,6,8,9,11,13,14,16,18,19,21,23,24,26,27,28,29,31,32]

λ> generables !! (10^6)

1250008

(generable x) se verifica si x es generable. Por ejemplo,

     generable 23       ==  True
     generable 77       ==  True
     generable 15       ==  False
     generable 1250008  ==  True
     generable 1250010  ==  False

generable 23 == True

generable 77 == True

generable 15 == False

generable 1250008 == True

generable 1250010 == False

(arbolGenerable x) es el árbol de los números generables menores o iguales a x. Por ejemplo,

     λ> putStrLn (drawTree (fmap show (arbolGenerable 11)))
     1
     |
     +- 3
     |  |
     |  +- 9
     |  |
     |  `- 8
     |
     `- 6
        |
        `- 11

λ> putStrLn (drawTree (fmap show (arbolGenerable 11)))

+- 3

| |

| +- 9

| |

| `- 8

`- 6

`- 11

Soluciones

import Graphics.Gnuplot.Simple

generables :: [Integer]
generables = 1 : mezcla [3 * x | x <- generables]
                        [5 + x | x <- generables]

-- (mezcla xs ys) es la lista ordenada obtenida mezclando las dos listas
-- ordenadas xs e ys, suponiendo que ambas son infinitas. Por ejemplo,
--    take 10 (mezcla [2,12..] [5,15..])  ==  [2,5,12,15,22,25,32,35,42,45]
--    take 10 (mezcla [2,22..] [5,15..])  ==  [2,5,15,22,25,35,42,45,55,62]
mezcla :: Ord a => [a] -> [a] -> [a]
mezcla us@(x:xs) vs@(y:ys)
  | x < y     = x : mezcla xs vs
  | x == y    = x : mezcla xs ys
  | otherwise = y : mezcla us ys

generable :: Integer -> Bool
generable x =
  x == head (dropWhile (<x) generables)

-- 2ª definición
generable2 :: Integer -> Bool
generable2 1 = True
generable2 x =    (x `mod` 3 == 0 && generable2 (x `div` 3))
               || (x > 5 && generable2 (x - 5))

generables2 :: [Integer] 
generables2 = filter generable2 [1..]

arbolGenerable :: Integer -> Tree Integer
arbolGenerable n = aux 1
  where aux x
          | 3*x <= n && 5+x <= n = Node x [aux (3*x), aux (5+x)] 
          | 3*x <= n             = Node x [aux (3*x)]
          | 5+x <= n             = Node x [aux (5+x)]
          | otherwise            = Node x [] 

-- 3ª definición
generable3 :: Integer -> Bool
generable3 x =
  x `elem` arbolGenerable x

import Graphics.Gnuplot.Simple

generables :: [Integer]

generables = 1 : mezcla [3 * x | x <- generables]

[5 + x | x <- generables]

-- (mezcla xs ys) es la lista ordenada obtenida mezclando las dos listas

-- ordenadas xs e ys, suponiendo que ambas son infinitas. Por ejemplo,

-- take 10 (mezcla [2,12..] [5,15..]) == [2,5,12,15,22,25,32,35,42,45]

-- take 10 (mezcla [2,22..] [5,15..]) == [2,5,15,22,25,35,42,45,55,62]

mezcla :: Ord a => [a] -> [a] -> [a]

mezcla us@(x:xs) vs@(y:ys)

| x < y = x : mezcla xs vs

| x == y = x : mezcla xs ys

| otherwise = y : mezcla us ys

generable :: Integer -> Bool

generable x =

x == head (dropWhile (<x) generables)

-- 2ª definición

generable2 :: Integer -> Bool

generable2 1 = True

generable2 x = (x `mod` 3 == 0 && generable2 (x `div` 3))

|| (x > 5 && generable2 (x - 5))

generables2 :: [Integer]

generables2 = filter generable2 [1..]

arbolGenerable :: Integer -> Tree Integer

arbolGenerable n = aux 1

where aux x

| 3*x <= n && 5+x <= n = Node x [aux (3*x), aux (5+x)]

| 3*x <= n = Node x [aux (3*x)]

| 5+x <= n = Node x [aux (5+x)]

| otherwise = Node x []

-- 3ª definición

generable3 :: Integer -> Bool

generable3 x =

x `elem` arbolGenerable x

5 Comentarios

import Data.Tree

generables :: [Integer]
generables = t
    where t = 1:[ x | x <- int (map (*3) t) (map (+5) t)]
          int (x:xs) (y:ys) | x < y = x:int xs (y:ys)
                            | x > y = y:int (x:xs) ys
                            | otherwise = x:int xs ys

generable :: Integer -> Bool                              
generable x = x == head (dropWhile (x>) generables)

arbolGenerable :: Integer -> Tree Integer
arbolGenerable x = aux 1 x
     where aux a x | 3*a > x && 5 + a > x = Node a []
                   | 3*a > x = Node a [aux (5+a) x]
                   | 5 + a > x = Node a [aux (3*a) x]
                   | otherwise = Node a [aux (3*a) x, aux (5+a) x]

import Data.Tree

generables :: [Integer]

generables = t

where t = 1:[ x | x <- int (map (*3) t) (map (+5) t)]

int (x:xs) (y:ys) | x < y = x:int xs (y:ys)

| x > y = y:int (x:xs) ys

| otherwise = x:int xs ys

generable :: Integer -> Bool

generable x = x == head (dropWhile (x>) generables)

arbolGenerable :: Integer -> Tree Integer

arbolGenerable x = aux 1 x

where aux a x | 3*a > x && 5 + a > x = Node a []

| 3*a > x = Node a [aux (5+a) x]

| 5 + a > x = Node a [aux (3*a) x]

| otherwise = Node a [aux (3*a) x, aux (5+a) x]

Responder

import Data.Tree 


generables :: [Integer]
generables = 1:[x | x <- [2..], generable x]

generable :: Integer -> Bool
generable n = aux 1 3 5 n
   where aux x 3 5 n | x + 5 == n || x*3 == n = True
                     | x+5 < n || x*3 < n =  aux (x+5) 3 5 n || aux (x*3) 3 5 n
                     | otherwise = False

arbolGenerable :: Integer ->  Tree Integer
arbolGenerable x = arbolixi 1 x
   where arbolixi  n x | (n*3) > x &&  (n+5) > x = Node n []
                       | (n*3) > x = Node n [arbolixi (n+5) x]
                       | (n+5) > x = Node n [arbolixi (n*3) x]
                       | otherwise = Node n [arbolixi (n*3) x, arbolixi (n+5) x ]

import Data.Tree

generables :: [Integer]

generables = 1:[x | x <- [2..], generable x]

generable :: Integer -> Bool

generable n = aux 1 3 5 n

where aux x 3 5 n | x + 5 == n || x*3 == n = True

| x+5 < n || x*3 < n = aux (x+5) 3 5 n || aux (x*3) 3 5 n

| otherwise = False

arbolGenerable :: Integer -> Tree Integer

arbolGenerable x = arbolixi 1 x

where arbolixi n x | (n*3) > x && (n+5) > x = Node n []

| (n*3) > x = Node n [arbolixi (n+5) x]

| (n+5) > x = Node n [arbolixi (n*3) x]

| otherwise = Node n [arbolixi (n*3) x, arbolixi (n+5) x ]

Responder

generables :: [Integer]
generables = 1 : intercala (map (+5) g) (map (*3) g)
           where
            g = generables
            intercala (x:xs) (y:ys) | x < y     = x:intercala xs (y:ys)
                                    | x > y     = y:intercala (x:xs) ys
                                    | otherwise = x:intercala xs ys


generable :: Integer -> Bool
generable n = n == (head . dropWhile (<n)) generables

generable2 :: Integer -> Bool
generable2 1 = True
generable2 n | n `mod` 3 == 0 = generable (n `div` 3) || generable (n-5)
             | n < 1          = False
             | otherwise      = generable (n - 5)

prop_generable :: Positive Integer -> Bool
prop_generable (Positive n) = generable n == generable2 n

-- *Main> quickCheck prop_generable
-- +++ OK, passed 100 tests.

generables :: [Integer]

generables = 1 : intercala (map (+5) g) (map (*3) g)

where

g = generables

intercala (x:xs) (y:ys) | x < y = x:intercala xs (y:ys)

| x > y = y:intercala (x:xs) ys

| otherwise = x:intercala xs ys

generable :: Integer -> Bool

generable n = n == (head . dropWhile (<n)) generables

generable2 :: Integer -> Bool

generable2 1 = True

generable2 n | n `mod` 3 == 0 = generable (n `div` 3) || generable (n-5)

| n < 1 = False

| otherwise = generable (n - 5)

prop_generable :: Positive Integer -> Bool

prop_generable (Positive n) = generable n == generable2 n

-- *Main> quickCheck prop_generable

-- +++ OK, passed 100 tests.

Responder

generables :: [Integer]
generables = [1,3,6,8,9,11,13,14,16,18,19,21,23,24] ++ (noM5 [26..])
            where noM5 (x:xs) | rem x 5 == 0 = noM5 xs
                             | otherwise = x : noM5 xs

generable :: Integer -> Bool
generable x | elem x [2,4,7,12,17,22] || rem x 5 == 0 = False
            | otherwise = True

generables :: [Integer]

generables = [1,3,6,8,9,11,13,14,16,18,19,21,23,24] ++ (noM5 [26..])

where noM5 (x:xs) | rem x 5 == 0 = noM5 xs

| otherwise = x : noM5 xs

generable :: Integer -> Bool

generable x | elem x [2,4,7,12,17,22] || rem x 5 == 0 = False

| otherwise = True

Responder

import Data.Tree

generables :: [Integer]
generables = 1 : ordena (map (+5) xs) (map (*3) xs)
           where xs = generables

ordena :: [Integer] -> [Integer] -> [Integer]
ordena a@(x:xs) b@(y:ys) | x < y     = x : ordena xs b
                         | x == y    = x : ordena xs ys
                         | otherwise = y : ordena a ys

generable :: Integer -> Bool
generable x = x == head (dropWhile (<x) generables)

arbolGenerable :: Integer -> Tree Integer
arbolGenerable x = Node 1 (aux 1)
               where aux a | a5 > x && a3 <= x  = [Node a3 (aux a3)]
                           | a5 <= x && a3 > x  = [Node a5 (aux a5)] 
                           | a5 <= x && a3 <= x = [Node a3 (aux a3), Node a5 (aux a5)]
                           | otherwise          = []
                           where a3 = a * 3
                                 a5 = a + 5

import Data.Tree

generables :: [Integer]

generables = 1 : ordena (map (+5) xs) (map (*3) xs)

where xs = generables

ordena :: [Integer] -> [Integer] -> [Integer]

ordena a@(x:xs) b@(y:ys) | x < y = x : ordena xs b

| x == y = x : ordena xs ys

| otherwise = y : ordena a ys

generable :: Integer -> Bool

generable x = x == head (dropWhile (<x) generables)

arbolGenerable :: Integer -> Tree Integer

arbolGenerable x = Node 1 (aux 1)

where aux a | a5 > x && a3 <= x = [Node a3 (aux a3)]

| a5 <= x && a3 > x = [Node a5 (aux a5)]

| a5 <= x && a3 <= x = [Node a3 (aux a3), Node a5 (aux a5)]

| otherwise = []

where a3 = a * 3

a5 = a + 5

Responder

Por 3 o más 5

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