# Euler Solution 73

### From ProgSoc Wiki

(Difference between revisions)

(Another easter egg.) |
(→Solutions for Problem 73) |
||

Line 3: | Line 3: | ||

'''NOTE:''' Another easter egg for the next person who solves it (no links/updates on the [[ Euler | main page]]). | '''NOTE:''' Another easter egg for the next person who solves it (no links/updates on the [[ Euler | main page]]). | ||

- | How many fractions are there of the form <i>n</i>/<i>d</i> (where <i>n</i> and <i>d</i> are positive integers with no common divisors) between 1/3 and 1/2 for <i>d</i> < | + | How many fractions are there of the form <i>n</i>/<i>d</i> (where <i>n</i> and <i>d</i> are positive integers with no common divisors) between 1/3 and 1/2 for <i>d</i> < 12001? |

+ | Note: Limit was increased lately from 10,000 to 12,000. (Thomas's won't work now, or will at least need it's limit adjusted) | ||

== Haskell by SanguineV == | == Haskell by SanguineV == | ||

Line 27: | Line 28: | ||

This is a slow brute force approach, can be done a lot faster! | This is a slow brute force approach, can be done a lot faster! | ||

+ | |||

+ | == Pyhton by Althalus == | ||

+ | Runtime: 496.6 seconds. Horrible. | ||

+ | third = 1.0/3 | ||

+ | half = 1.0/2 | ||

+ | fractions = {} | ||

+ | for d in range(1,12001): | ||

+ | if d % 100 == 0: print d | ||

+ | for n in range(1,d): | ||

+ | tmp = float(n)/d | ||

+ | if tmp > third and tmp < half: | ||

+ | f = gcd(n,d) | ||

+ | fractions[(n/f,d/f)] = 1 | ||

+ | print len(fractions.keys()) | ||

[[Category: Euler]] | [[Category: Euler]] |

## Revision as of 09:30, 24 April 2010

# Solutions for Problem 73

**NOTE:** Another easter egg for the next person who solves it (no links/updates on the main page).

How many fractions are there of the form *n*/*d* (where *n* and *d* are positive integers with no common divisors) between 1/3 and 1/2 for *d* < 12001?

Note: Limit was increased lately from 10,000 to 12,000. (Thomas's won't work now, or will at least need it's limit adjusted)

## Haskell by SanguineV

Runtime: unknown

{- Return all the fractions i in the range 1/3 < i < 1/2 for some divisor "n" - Note: results are sorted by default. -} fracs :: Double -> [Double] fracs n = map (\x -> x/n) (takeWhile (< n/2) (dropWhile (<= n/3) [1..])) {- Combine two sorted lists of doubles (can also use type: Eq a => [a] -> [a] -> [a]) - returning a sorted single list without duplicates. -} comb :: [Double] -> [Double] -> [Double] comb [] ys = ys comb xs [] = xs comb (x:xs) (y:ys) | x == y = [x] ++ (comb xs ys) comb (x:xs) (y:ys) | x > y = [y] ++ (comb (x:xs) ys) comb (x:xs) (y:ys) = [x] ++ (comb xs (y:ys)) {- Combine all the lists together for divisor 5..10000 and print the length -} main = print (length (foldl (\l n -> comb l (fracs n)) [] [5..10000]))

This is a slow brute force approach, can be done a lot faster!

## Pyhton by Althalus

Runtime: 496.6 seconds. Horrible.

third = 1.0/3 half = 1.0/2 fractions = {} for d in range(1,12001): if d % 100 == 0: print d for n in range(1,d): tmp = float(n)/d if tmp > third and tmp < half: f = gcd(n,d) fractions[(n/f,d/f)] = 1 print len(fractions.keys())