Another Project Euler... (apologies)
#73 http://projecteuler.net/problem=73
I found this one more tricky than it first seems.
My attempt fails.
My reasoning of solution. Trying to find all reduced fractions with denominator
and numerator in range 1... 12000 that are greater than 1/3 but less than
1/2.The most naive way would be to make a 12000x12000 grid of fractions,
nubbing out duplicates. I tried this, and as I expected I ran out of memory.
One problem is duplicates. To get rid of duplicate fractions, for all y <12000,
I only want to check fractions with numerators x (i.e. fractions xry), where x
and y are coprime.(e.g so 1/2 will only be counted once, and not 3/6, 4/8 etc)
My method:
NB. check coprime
coprime =. =&0@:(+/)@:(e.&q:)
NB. get coprimes. (since index starts at zero, and we do not want to compare
with 0 or 1, we start at index 2
NB. and then +2 to get the coprime number.
gcp =. >:@: >:@:I.@: (coprime"(0 0))(}.@:>:@: i.)
e.g. gcp 12 returns 5 7 11.
Next,
NB. get fractions between 1/3 and 1/2
fracs =. +/@:,@:(1r3&<*.1r2&>)@:(%~ func2"0)
If I test for 2 3 4 5 6 7 8 to see how many fractions are between 1/3 and 1/2I
get
fracs >: i.8
3
This is the same value as shown on the question webpage for the value d=8.For d
= 12000if I run the verb, I get an out of memory error.Any ideas how to
proceed? I am wondering if my approach is salvageable, or I need to go back to
the drawing board.
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
