# Euler Solution 119

(Difference between revisions)
 Revision as of 04:49, 5 April 2012 (view source)Althalus (Talk | contribs) (→Solutions for Problem 119)← Older edit Latest revision as of 04:56, 5 April 2012 (view source)Althalus (Talk | contribs) m (→Python by Althalus) Line 38: Line 38: candidates = [] candidates = [] + # initially tried counting up from a, 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 x in range(2,100): for y in range(2, 50): for y in range(2, 50):

# 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 = []
# initially tried counting up from a, 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
```