Hi all - apologies in advance since this issue is not necessarily a

Ruby issue, but I’ve written the program in Ruby and the community

here has been very helpful/friendly in my experience.

I’m working on another problem from Project Euler (

). This one is problem 73 (I’m not actually that smart, I just jump

around ):

“Consider the fraction, n/d, where n and d are positive integers. If

nd and HCF(n,d)=1, it is called a reduced proper fraction. How many

fractions lie between 1/3 and 1/2 in the sorted set of reduced proper

fractions for d 10,000?”

So I set up an hcf(n,d) function that prime-factor-izes n and d to see

if n/d is reduced and proper:

Primes_under_100 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,

43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

def hcf(n,d)

Primes_under_100.each do |prime|

if (prime < Math.sqrt(d) &&

n % prime == 0 &&

d % prime == 0) ||

d % n == 0

return 2

end

end

return 1

end

Then I ran that through a loop that builds an array of unique

instances of fractions between 1/2 and 1/3:

red_prop_fract = []

for d in 2…10_000 do

for n in 1…d do

if hcf(n,d) == 1 && n.to_f/d > 1.0/3 && n.to_f/d < 0.5

red_prop_fract.push(n.to_f/d) unless red_prop_fract.include?

(n.to_f/d)

end

end

end

#Get the answer

p red_prop_fract.length

Now, I’m fairly certain that the algorithm is right, because I ran it

on their example of d < 9 and got the correct answer. However, this

setup is taking ridiculously long and I can’t determine why. Running

on a computer with a 2.4GHz CPU and 256 Mb of RAM, I started it at

4:30 yesterday and it hasn’t terminated!

I know that a nested ‘for’ loop that goes to n is O(n^2). And I know

that the array I’m building is rather big, and growing it gradually is

going to cause a lot of allocations and GCs. But I can’t figure out

why it’s being so ridiculous.

My first rule as a programmer is “Assume all problems are my fault.”

Insights?

TIA,

Andrew