Euler Solution 73

From ProgSoc Wiki

(Difference between revisions)
Jump to: navigation, search
(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> < 10001?
+
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())
Personal tools