Personal tools

Euler problems/61 to 70

From HaskellWiki

< Euler problems(Difference between revisions)
Jump to: navigation, search
(Problem 67 reads into memory, separates parsing)
m (Corrected the links to the Euler project)
Line 1: Line 1:
 
[[Category:Programming exercise spoilers]]
 
[[Category:Programming exercise spoilers]]
== [http://projecteuler.net/index.php?section=problems&id=61 Problem 61] ==
+
== [http://projecteuler.net/index.php?section=view&id=61 Problem 61] ==
 
Find the sum of the only set of six 4-digit figurate numbers with a cyclic property.
 
Find the sum of the only set of six 4-digit figurate numbers with a cyclic property.
   
Line 8: Line 8:
 
</haskell>
 
</haskell>
   
== [http://projecteuler.net/index.php?section=problems&id=62 Problem 62] ==
+
== [http://projecteuler.net/index.php?section=view&id=62 Problem 62] ==
 
Find the smallest cube for which exactly five permutations of its digits are cube.
 
Find the smallest cube for which exactly five permutations of its digits are cube.
   
Line 16: Line 16:
 
</haskell>
 
</haskell>
   
== [http://projecteuler.net/index.php?section=problems&id=63 Problem 63] ==
+
== [http://projecteuler.net/index.php?section=view&id=63 Problem 63] ==
 
How many n-digit positive integers exist which are also an nth power?
 
How many n-digit positive integers exist which are also an nth power?
   
Line 28: Line 28:
 
</haskell>
 
</haskell>
   
== [http://projecteuler.net/index.php?section=problems&id=64 Problem 64] ==
+
== [http://projecteuler.net/index.php?section=view&id=64 Problem 64] ==
 
How many continued fractions for N ≤ 10000 have an odd period?
 
How many continued fractions for N ≤ 10000 have an odd period?
   
Line 36: Line 36:
 
</haskell>
 
</haskell>
   
== [http://projecteuler.net/index.php?section=problems&id=65 Problem 65] ==
+
== [http://projecteuler.net/index.php?section=view&id=65 Problem 65] ==
 
Find the sum of digits in the numerator of the 100th convergent of the continued fraction for e.
 
Find the sum of digits in the numerator of the 100th convergent of the continued fraction for e.
   
Line 51: Line 51:
 
</haskell>
 
</haskell>
   
== [http://projecteuler.net/index.php?section=problems&id=66 Problem 66] ==
+
== [http://projecteuler.net/index.php?section=view&id=66 Problem 66] ==
 
Investigate the Diophantine equation x<sup>2</sup> − Dy<sup>2</sup> = 1.
 
Investigate the Diophantine equation x<sup>2</sup> − Dy<sup>2</sup> = 1.
   
Line 59: Line 59:
 
</haskell>
 
</haskell>
   
== [http://projecteuler.net/index.php?section=problems&id=67 Problem 67] ==
+
== [http://projecteuler.net/index.php?section=view&id=67 Problem 67] ==
 
Using an efficient algorithm find the maximal sum in the triangle?
 
Using an efficient algorithm find the maximal sum in the triangle?
   
Line 81: Line 81:
 
</haskell>
 
</haskell>
   
== [http://projecteuler.net/index.php?section=problems&id=68 Problem 68] ==
+
== [http://projecteuler.net/index.php?section=view&id=68 Problem 68] ==
 
What is the maximum 16-digit string for a "magic" 5-gon ring?
 
What is the maximum 16-digit string for a "magic" 5-gon ring?
   
Line 89: Line 89:
 
</haskell>
 
</haskell>
   
== [http://projecteuler.net/index.php?section=problems&id=69 Problem 69] ==
+
== [http://projecteuler.net/index.php?section=view&id=69 Problem 69] ==
 
Find the value of n ≤ 1,000,000 for which n/φ(n) is a maximum.
 
Find the value of n ≤ 1,000,000 for which n/φ(n) is a maximum.
   
Line 97: Line 97:
 
</haskell>
 
</haskell>
   
== [http://projecteuler.net/index.php?section=problems&id=70 Problem 70] ==
+
== [http://projecteuler.net/index.php?section=view&id=70 Problem 70] ==
 
Investigate values of n for which φ(n) is a permutation of n.
 
Investigate values of n for which φ(n) is a permutation of n.
   

Revision as of 13:52, 20 July 2007

Contents

1 Problem 61

Find the sum of the only set of six 4-digit figurate numbers with a cyclic property.

Solution:

problem_61 = undefined

2 Problem 62

Find the smallest cube for which exactly five permutations of its digits are cube.

Solution:

problem_62 = undefined

3 Problem 63

How many n-digit positive integers exist which are also an nth power?

Solution: Since dn has at least n+1 digits for any d≥10, we need only consider 1 through 9. If dn has fewer than n digits, every higher power of d will also be too small since d < 10. We will also never have n+1 digits for our nth powers. All we have to do is check dn for each d in {1,...,9}, trying n=1,2,... and stopping when dn has fewer than n digits.

problem_63 = length . concatMap (takeWhile (\(n,p) -> n == nDigits p))
             $ [powers d | d <- [1..9]]
    where powers d = [(n, d^n) | n <- [1..]]
          nDigits n = length (show n)

4 Problem 64

How many continued fractions for N ≤ 10000 have an odd period?

Solution:

problem_64 = undefined

5 Problem 65

Find the sum of digits in the numerator of the 100th convergent of the continued fraction for e.

Solution:

import Data.Ratio
 
problem_65 = dsum . numerator . contFrac . take 100 $ e
    where dsum 0 = 0
          dsum n = let ( d, m ) = n `divMod` 10 in m + ( dsum d )
          contFrac = foldr1 (\x y -> x + 1/y)
          e = 2 : 1 : insOnes [2,4..]
          insOnes (x:xs) = x : 1 : 1 : insOnes xs

6 Problem 66

Investigate the Diophantine equation x2 − Dy2 = 1.

Solution:

problem_66 = undefined

7 Problem 67

Using an efficient algorithm find the maximal sum in the triangle?

Solution:

import System.Process
import IO
 
slurpURL url = do
    (_,out,_,_) <- runInteractiveCommand $ "curl " ++ url
    hGetContents out
 
problem_67 = do
    src <- slurpURL "http://projecteuler.net/project/triangle.txt"
    print $ head $ foldr1 g $ parse src
    where
        parse :: String -> [[Int]]
        parse s = map ((map read).words) $ lines s
        f x y z = x + max y z
        g xs ys = zipWith3 f xs ys $ tail ys

8 Problem 68

What is the maximum 16-digit string for a "magic" 5-gon ring?

Solution:

problem_68 = undefined

9 Problem 69

Find the value of n ≤ 1,000,000 for which n/φ(n) is a maximum.

Solution:

problem_69 = undefined

10 Problem 70

Investigate values of n for which φ(n) is a permutation of n.

Solution:

problem_70 = undefined