# Euler Solution 119

(Difference between revisions)
 Revision as of 08:36, 7 May 2009 (view source)← Older edit Revision as of 04:49, 5 April 2012 (view source)Althalus (Talk | contribs) (→Solutions for Problem 119)Newer edit → Line 31: Line 31: '''Note:''' The trick to an efficient implementation is by searching based on the sum of the digits, not the actual number n. '''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 = [] + 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] + [[Category: Euler]] [[Category: Euler]]

# 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.

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 = []
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]
```