Euler Solution 63

From ProgSoc Wiki

Jump to: navigation, search

Solutions for Problem 63

How many n digit numbers are there that are also an nth power?

i.e. xn = d1d2...dn

where 1 <= x <= 9 (i.e. a single-digit positive integer)

Haskell by SanguineV

Runtime: 7.979 ms (on aglaope)

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

{- Return the number of numbers with "n" digits that are also an "n"th power -}
numDigPow :: Integer -> Int
numDigPow n = length (takeWhile (< lowLim * 10) (dropWhile (< lowLim)
                                                (map (\x -> pow x n) [1..])))
  where
    lowLim = (pow 10 (n - 1))

{- Calculate the number of n digit nth powers for n starting from 1, take until
 - the number is 0. Sum these and print the result. -}
main = print (sum (takeWhile (> 0) (map (\x -> numDigPow x) [1..])))

Ruby by tomchristmas

Runtime: 11ms

A brief description of line three by Dr. D. Scribe of the Expla Nation:

"For any integer n >= 1

10n - 1 <= xn < 10n

i.e. xn is an n-digit integer.

If we let xn = 10n - 1 and then make n the subject, we get:

n = log 10 / (log 10 - log x)

The floor value of n (greatest integer less than or equal to n) will give us the maximum number of digits xn can hold for each integer value of x in the range 1 <= x <= 9."

nums = 0

1.upto(9){|x|	
  1.upto((Math.log(10)/(Math.log(10)-Math.log(x))).floor){|n|
    if (x ** n).to_s.length == n
       nums += 1
       puts "#{x} ^ #{n} = #{x ** n}"
    end
  }
}

puts nums
Personal tools