Números taxicab

Los números taxicab, taxi-cab o números de Hardy-Ramanujan son aquellos números naturales que pueden expresarse como suma de dos cubos de más de una forma.

Alternativamente, se define al n-ésimo número taxicab como el menor número que es suma de dos cubos de n formas.

Definir las siguientes sucesiones

   taxicab  :: [Integer]
   taxicab2 :: [Integer]

1 2	taxicab :: [Integer] taxicab2 :: [Integer]

tales que taxicab es la sucesión de estos números según la primera definición y taxicab2 según la segunda. Por ejemplo,

   take 5 taxicab   ==  [1729,4104,13832,20683,32832]
   take 2 taxicab2  ==  [2,1729]

1 2	take 5 taxicab == [1729,4104,13832,20683,32832] take 2 taxicab2 == [2,1729]

Nota 1. La sucesiones taxicab y taxicab2 se corresponden con las sucesiones A001235 y A011541 de la OEIS.

Nota 2: Este ejercicio ha sido propuesto por Ángel Ruiz Campos.

Soluciones

import Data.List  (find)
import Data.Maybe (fromJust)

taxicab :: [Integer]
taxicab = filter ((> 1) . length . descomposiciones) [1..]

-- (descomposiciones n) es la lista de pares (x,y) tal que x³ + y³ = n.
-- Por ejemplo,
--    descomposiciones 1729  ==  [(10,9),(12,1)]
--    descomposiciones 1728  ==  [(12,0)]
descomposiciones :: Integer -> [(Integer,Integer)]
descomposiciones n =
  [(x,y) | x <- [1..round (fromIntegral n ** (1/3))],
           let z = n - x^3,
           let z' = round (fromIntegral z ** (1/3)),
           z'^3 == z,
           let y = z',
           y <= x]

-- 2ª definición de descomposiciones
descomposiciones2 :: Integer -> [(Integer,Integer)]
descomposiciones2 n =
  [(x,y) | x <- [1..raizEnt n 3],
           let z = n - x^3,
           let y = raizEnt z 3,
           y <= x,    
           y^3 == z]

-- (raizEnt x n) es la raíz entera n-ésima de x; es decir, el mayor
-- número entero y tal que y^n <= x. Por ejemplo, 
--    raizEnt  8 3      ==  2
--    raizEnt  9 3      ==  2
--    raizEnt 26 3      ==  2
--    raizEnt 27 3      ==  3
--    raizEnt (10^50) 2 ==  10000000000000000000000000
-- ---------------------------------------------------------------------

raizEnt :: Integer -> Integer -> Integer
raizEnt x n = 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^n

taxicab2 :: [Integer]
taxicab2 = aux 1 [2..]
  where aux n xs = fx : aux (n+1) [fx+1..]
          where fx = fromJust (find ((== n) . length . descomposiciones) xs)

import Data.List (find)

import Data.Maybe (fromJust)

taxicab :: [Integer]

taxicab = filter ((> 1) . length . descomposiciones) [1..]

-- (descomposiciones n) es la lista de pares (x,y) tal que x³ + y³ = n.

-- Por ejemplo,

-- descomposiciones 1729 == [(10,9),(12,1)]

-- descomposiciones 1728 == [(12,0)]

descomposiciones :: Integer -> [(Integer,Integer)]

descomposiciones n =

[(x,y) | x <- [1..round (fromIntegral n ** (1/3))],

let z = n - x^3,

let z' = round (fromIntegral z ** (1/3)),

z'^3 == z,

let y = z',

y <= x]

-- 2ª definición de descomposiciones

descomposiciones2 :: Integer -> [(Integer,Integer)]

descomposiciones2 n =

[(x,y) | x <- [1..raizEnt n 3],

let z = n - x^3,

let y = raizEnt z 3,

y <= x,

y^3 == z]

-- (raizEnt x n) es la raíz entera n-ésima de x; es decir, el mayor

-- número entero y tal que y^n <= x. Por ejemplo,

-- raizEnt 8 3 == 2

-- raizEnt 9 3 == 2

-- raizEnt 26 3 == 2

-- raizEnt 27 3 == 3

-- raizEnt (10^50) 2 == 10000000000000000000000000

-- ---------------------------------------------------------------------

raizEnt :: Integer -> Integer -> Integer

raizEnt x n = 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^n

taxicab2 :: [Integer]

taxicab2 = aux 1 [2..]

where aux n xs = fx : aux (n+1) [fx+1..]

where fx = fromJust (find ((== n) . length . descomposiciones) xs)

2 Comentarios

No es muy eficiente

taxicab  :: [Integer]
taxicab = [x | x<-[1..], esTaxicab x]
esTaxicab x = not(null (xs x)) && not(null (tail (xs x)))
xs x =  borra [(y,z) | y < -[1..(floor ((fromInteger x)**(1/3)))], z < -[1..(floor ((fromInteger)x**(1/3)))], y^3+z^3==x]
borra [] =  []
borra [p] = [p]
borra ((x,y):z:xs) = aux []((x,y):z:xs)
  where aux [] (p:ys) = aux [p] ys
        aux zs [] = zs
        aux zs [(a,b)]  | (a,b)`elem`zs || (b,a)`elem`zs =  zs 
                          | otherwise =  ((b,a):zs) 
        aux zs ((a,b):ys) | (a,b)`elem`zs || (b,a)`elem`zs = aux zs ys
                          | otherwise = aux ((b,a):zs) ys


taxicab2 :: [Integer]
taxicab2 =2: [head [x | x < -taxicab, length (xs x)==y]| y < -[2..]]

taxicab :: [Integer]

taxicab = [x | x<-[1..], esTaxicab x]

esTaxicab x = not(null (xs x)) && not(null (tail (xs x)))

xs x = borra [(y,z) | y < -[1..(floor ((fromInteger x)**(1/3)))], z < -[1..(floor ((fromInteger)x**(1/3)))], y^3+z^3==x]

borra [] = []

borra [p] = [p]

borra ((x,y):z:xs) = aux []((x,y):z:xs)

where aux [] (p:ys) = aux [p] ys

aux zs [] = zs

aux zs [(a,b)] | (a,b)`elem`zs || (b,a)`elem`zs = zs

| otherwise = ((b,a):zs)

aux zs ((a,b):ys) | (a,b)`elem`zs || (b,a)`elem`zs = aux zs ys

| otherwise = aux ((b,a):zs) ys

taxicab2 :: [Integer]

taxicab2 =2: [head [x | x < -taxicab, length (xs x)==y]| y < -[2..]]

Responder

Tampoco demasiado rápida jummm…

taxicab :: [Integer]
taxicab = Prelude.filter (\x -> (length (sumasComoCubos x) > 1)) [1..]

taxicab2 :: [Integer]
taxicab2 = 2:[head [x | x <- taxicab, length (sumasComoCubos x) == y]| y <- [2..]]

sumasComoCubos :: Integer -> [(Integer,Integer)]
sumasComoCubos n = [(round $ fromIntegral b**(1/3),a) | a<-[cubicRoot, cubicRoot-1..cubicRoot2], let b = fromIntegral (n-a^3), checkB b]
  where cubicRoot  = floor(fromIntegral n**(1/3))
        cubicRoot2 = ceiling(fromIntegral n**(1/3)/(2**(1/3)))
        checkB x = x/=0 && (round (fromIntegral x ** (1/3))) ^ 3 == x

taxicab :: [Integer]

taxicab = Prelude.filter (\x -> (length (sumasComoCubos x) > 1)) [1..]

taxicab2 :: [Integer]

taxicab2 = 2:[head [x | x <- taxicab, length (sumasComoCubos x) == y]| y <- [2..]]

sumasComoCubos :: Integer -> [(Integer,Integer)]

sumasComoCubos n = [(round $ fromIntegral b**(1/3),a) | a<-[cubicRoot, cubicRoot-1..cubicRoot2], let b = fromIntegral (n-a^3), checkB b]

where cubicRoot = floor(fromIntegral n**(1/3))

cubicRoot2 = ceiling(fromIntegral n**(1/3)/(2**(1/3)))

checkB x = x/=0 && (round (fromIntegral x ** (1/3))) ^ 3 == x

Responder

Números taxicab

Soluciones

2 Comentarios

Leave a Reply to alerodrod5Cancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

2 Comentarios

Leave a Reply to alerodrod5Cancel reply

Entradas recientes

Buscar

Correo electrónico