Menu Close

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]

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]

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)
Medio

2 soluciones de “Números taxicab

  1. alerodrod5

    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..]]
  2. jaibengue

    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

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.