# Euler problems/61 to 70

### From HaskellWiki

(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= | + | == [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= | + | == [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= | + | == [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= | + | == [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= | + | == [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= | + | == [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= | + | == [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= | + | == [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= | + | == [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= | + | == [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 d^{n} has at least n+1 digits for any d≥10, we need only consider 1 through 9. If d^{n} 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 d^{n} for each d in {1,...,9}, trying n=1,2,... and stopping when d^{n} 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 x^{2} − Dy^{2} = 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