Ir al contenido principal

Sumas de potencias de 3 primos

Los primeros números de la forma p²+q³+r⁴, con p, q y r primos son

28 = 2² + 2³ + 2
33 = 3² + 2³ + 2
47 = 2² + 3³ + 2
49 = 5² + 2³ + 2

Definir la sucesión

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,

λ> take 15 sumas3potencias
[28,33,47,49,52,68,73,92,93,98,112,114,117,133,138]
λ> sumas3potencias !! 234567
8953761

Soluciones

import Data.Numbers.Primes (primes)

-- The function diag merges an unbounded list of increasing unbounded
-- lists which are in increasing order of first element. Duplicate
-- elements are removed.

diag ((a:as):bss) = a:merge as (diag bss)

merge (a:as) (b:bs) = case compare a b of
                      LT -> a:merge as (b:bs)
                      EQ -> merge as (b:bs)
                      GT -> b:merge (a:as) bs

-- And used to generate the ordered list of sums of two increasing
-- sequences:

map2 f as bs = [map (f a) bs | a<-as]

ordsums as bs = diag $ map2 (+) as bs

-- The result then is just to count all the sums until we hit the limit:

sumas3potencias :: [Integer]
sumas3potencias =
    foldr1 ordsums $ map2 (flip (^)) [4,3,2] primes