Euler Solution 119

From ProgSoc Wiki

(Difference between revisions)
Jump to: navigation, search
(Solutions for Problem 119)
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 <i>n</i>.
'''Note:''' The trick to an efficient implementation is by searching based on the sum of the digits, not the actual number <i>n</i>.
 +
 +
== 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]]

Revision as of 04:49, 5 April 2012

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