Euler Solution 119

From ProgSoc Wiki

Jump to: navigation, search

Solutions for Problem 119

Define an to be the nth number (of at least 2 digits) that is also the sum of the digits of n raised to some integer k. Find a30.

Haskell by SanguineV

Runtime: 12.983 ms

{- Find the sum of the digits of a number. -}
sumDigs :: Integer -> Integer
sumDigs n | n < 10 = n
sumDigs n = (mod n 10) + (sumDigs (div n 10))

{- Raise "n" to some power "p". -}
pow :: Integer -> Integer -> Integer
pow 1 n = n
pow p n = n * (pow (p - 1) n)

{- Given a power and a limit, search all numbers up to the limit raised to the power,
 - return those that satisfy n == (sumDigs n)^p. -}
sols4pow :: Integer -> Integer -> [Integer]
sols4pow p lim = map snd (filter (\(y,z) -> y == sumDigs z) (map (\x -> (x,pow p x)) [2..lim]))

{- Given a limit, find all numbers that satisfy the condition where the sum of the
 - digits is less than the limit and for powers 2..9 -}
e2ps :: Integer -> [Integer]
e2ps lim = foldl (\x y -> x ++ (sols4pow y lim)) [] [2..9]

{- Print the 30th element, using 100 as the limit for the sum of the digits. -}
main = print ((e2ps 100) !! 29)

Note: The trick to an efficient implementation is by searching based on the sum of the digits, not the actual number n.

Python by Althalus

Runtime: 0.3 seconds

digitsum = lambda x: sum(map(int, str(x)))

candidates = []
# initially tried counting up from a[10], but the numbers are just too big.
# far smarter and more likely to eventually finish if you start with the digit sums
for x in range(2,100):
    for y in range(2, 50):
        n = x**y
        if digitsum(n) == x:
            candidates.append(n)
candidates.sort()
print candidates[29]
Personal tools