Euler Solution 73

From ProgSoc Wiki

Revision as of 06:37, 25 April 2010 by Althalus (Talk | contribs)
Jump to: navigation, search

Contents

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 <= 12000?

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!

Python by Althalus

Runtime: 27.7 seconds. Using a (slightly modified) Stern-Brocot tree this time. Much faster, since we can instruct the tree to only give us the fractions between 1/2 and 1/3 by using those fractions as the starting point (instead of the original 0/1, 1/0)

import sys 
sys.setrecursionlimit(13001)
def sternbrocot_count(depth,lower,upper,n1=1,d1=0,n2=0,d2=1,curdepth=1):
    n = n1+n2
    d = d1+d2
    if n > d or d > depth: return 0
    if (float(n)/d < upper) and (float(n)/d > lower): 
        res = 1 
    else: res = 0 
    if curdepth < depth: 
        res += sternbrocot_count(depth,lower,upper,n,d,n2,d2,curdepth+1)
        res += sternbrocot_count(depth,lower,upper,n1,d1,n,d,curdepth+1)
    return res 

print sternbrocot_count(12000, 1.0/3, 1.0/2, 1,3, 1,2)

Original 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())

PLT-Scheme by Althalus

Runtime: 1.03s

Essentially the same logic as my python code above, in a language I don't really know. I'm surprised I got it to work at all. Whilst this particular version of scheme probably isn't currently on any of Progsoc's servers, I'm sure we could get someone to make it available on one of them...

#lang scheme

(define (stern-brocot depth n1 d1 n2 d2 curdepth)
  (define n (+ n1 n2))
  (define d (+ d1 d2))
  (cond
    [(or (> n d) (> d depth))
     0]
    [else
     (cond
       [(<= curdepth depth)
        (+ 1 (+ (stern-brocot depth n d n2 d2 (+ curdepth 1)) (stern-brocot depth n1 d1 n d (+ curdepth 1))))]
       [else 1])
     ])
)  
    
(stern-brocot 12000 1 3 1 2 1)
Personal tools