# Euler Solution 119

### From ProgSoc Wiki

(Difference between revisions)

(→Solutions for Problem 119) |
m (→Python by Althalus) |
||

Line 38: | Line 38: | ||

candidates = [] | 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 x in range(2,100): | ||

for y in range(2, 50): | for y in range(2, 50): |

## Latest revision as of 04:56, 5 April 2012

# Solutions for Problem 119

Define *a _{n}* to be the

*n*th number (of at least 2 digits) that is also the sum of the digits of

*n*raised to some integer

*k*. Find

*a*.

_{30}## 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]