Sumas de potencias de 3 primos
Los primeros números de la forma p²+q³+r⁴, con p, q y r primos son
1 2 3 4 |
28 = 2² + 2³ + 2⁴ 33 = 3² + 2³ + 2⁴ 47 = 2² + 3³ + 2⁴ 49 = 5² + 2³ + 2⁴ |
Definir la sucesión
1 |
sumas3potencias :: [Integer] |
cuyos elementos son los números que se pueden escribir de la forma p²+q³+r⁴, con p, q y r primos. Por ejemplo,
1 2 3 4 |
λ> take 15 sumas3potencias [28,33,47,49,52,68,73,92,93,98,112,114,117,133,138] λ> sumas3potencias !! 234567 8953761 |
Soluciones
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
import Data.Numbers.Primes (primes) -- 1ª solución -- =========== sumas3potencias1 :: [Integer] sumas3potencias1 = filter esTripleSuma [1..] -- (esTripleSuma n) se verifica si n se puede escribir de la forma -- p²+q³+r⁴, con p, q y r primos. Por ejemplo, -- esTripleSuma 33 == True -- esTripleSuma 45 == False esTripleSuma :: Integer -> Bool esTripleSuma = not . null . triplesSumas -- (triplesSumas n) es la lista de las ternas de primos (p,q,r) tales -- que p²+q³+r⁴ = n. Por ejemplo, -- triplesSumas 33 == [(3,2,2)] -- triplesSumas 145 == [(11,2,2),(2,5,2)] -- triplesSumas 45 == [] triplesSumas :: Integer -> [(Integer,Integer,Integer)] triplesSumas n = [(p,q,r) | r <- xs, q <- xs, let p2 = n - q^3 - r^4, let p = (floor . sqrt . fromIntegral) p2, p*p == p2, isPrime p] where xs = takeWhile (< (ceiling $ sqrt $ fromIntegral n)) primes -- 2ª solución -- =========== sumas3potencias2 :: [Integer] sumas3potencias2 = sumaOrdenadaInf as (sumaOrdenadaInf bs cs) sumaOrdenadaInf:: [Integer] -> [Integer] -> [Integer] sumaOrdenadaInf xs ys = mezclaTodas [map (+x) ys | x <- xs] mezclaTodas :: Ord a => [[a]] -> [a] mezclaTodas = foldr1 xmezcla where xmezcla (x:xs) ys = x : mezcla xs ys mezcla :: Ord a => [a] -> [a] -> [a] mezcla (x:xs) (y:ys) | x < y = x : mezcla xs (y:ys) | x == y = x : mezcla xs ys | x > y = y : mezcla (x:xs) ys as = map (^2) primes bs = map (^3) primes cs = map (^4) primes |
A mí me da 8560761
Misma solución pero usando un operador para sumar ordenadamente
n
listas queda más chulo :DLa diferencia se debe a que hay elementos repetidos. Por ejemplo,
El 145 aparece dos veces ya que se puede escribir como 11^2+2^3+2^4 y 2^2+5^3+2^4.
¡Claro, tienes razón! «números que» (no tripletas que), ya que reposteo, una generalización a
n
potencias ¡gracias!Igual que @fracruzam, otra función (generalizada a
n
potencias) para chequear un único número, es lo suficientemente rápida para revisar a lo burro el índice indicado en el enunciado (3 minutos usando 6 cores).