Euler Solution 73

From ProgSoc Wiki

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

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.

#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