I don't remember if and how I solved this - and the project Euler site is down - but it seems like a generative approach might be the way to go: for each numerator "n", consider only denominators between 2n and 3n.
On Mon, Jun 16, 2014 at 12:14 PM, Skip Cave <[email protected]> wrote: > It doesn't look like my approach of making a list of floating point > fractions between 1/2 and 1/3, converting to rationals, and eliminating > large numerators & denominators, is very practical. Even using a million > decimal fractions in evenly spaced steps between 1/2 and 1/3, that still > doesn't produce all the possible rational fractions between the two limits, > with numerators and denominators less than 12001. > > Skip Cave > Cave Consulting LLC > > > On Sun, Jun 15, 2014 at 11:41 PM, Skip Cave <[email protected]> > wrote: > > > Raul, you're right. I need a finer step between all the fractions, as my > > list is missing a few fractions. > > > > Skip > > > > Skip Cave > > Cave Consulting LLC > > > > > > On Sun, Jun 15, 2014 at 7:51 PM, Raul Miller <[email protected]> > > wrote: > > > >> This doesn't seem to represent any of these values: > >> 4993r11983 4988r11971 4983r11959 4978r11947 > >> > >> FYI, > >> > >> -- > >> Raul > >> > >> > >> > >> On Sun, Jun 15, 2014 at 8:15 PM, Skip Cave <[email protected]> > >> wrote: > >> > >> > Well, > >> > > >> > load 'strings' > >> > f =. x:1%2+10000%~i.10001 NB. Generate equal-spaced floating > >> fractions > >> > between 1/3 and 1/2 > >> > k =. 12001>".(": f) rplc ' ';',';'r';',' NB. Find all numerators > and > >> > denominators less than 12001 > >> > > >> > counts all numerators and denominators below 12000 as separate > entities. > >> > Unfortunately, that > >> > wasn't what the problem asked. > >> > > >> > In order to count only rational fractions between 0.5 & 0.333 where > both > >> > the numerator and the denominatorhave values of 12000 or less, we need > >> to > >> > add one more line to the program that pairs the > >> > numerator and denominator comparisons, and then "ands" them, to find > >> > fractions that have > >> > both the numerator and denominator below 12001. > >> > > >> > +/ *./"1(10001 2) $ k NB. And values pairwise & sum. > >> > > >> > That should get the correct answer. The whole thing takes less that 2 > >> > seconds to run on my machine. > >> > > >> > Skip > >> > > >> > > >> > > >> > > >> > Skip Cave > >> > Cave Consulting LLC > >> > > >> > > >> > On Sun, Jun 15, 2014 at 6:39 PM, Raul Miller <[email protected]> > >> > wrote: > >> > > >> > > I generally avoid project euler, because I do not like working under > >> its > >> > > constraint on disclosure. So I'm pleased when something leaks out > >> that I > >> > > can play with. But I also try to live within the implied spirit of > the > >> > > contest, so I'm not going to release my code. > >> > > > >> > > Still: a quick calculation suggests that J's floating point > >> > representation > >> > > is adequate for this problem (and gives a 30x speed improvement over > >> use > >> > of > >> > > rationals). Also, a trivial approach seems plenty adequate here > >> > > > >> > > Thanks, > >> > > > >> > > -- > >> > > Raul > >> > > > >> > > > >> > > > >> > > On Sun, Jun 15, 2014 at 7:07 PM, David Lambert < > >> [email protected]> > >> > > wrote: > >> > > > >> > > > On 15/06/2014 16:59, Jon Hough wrote: > >> > > >> > >> > > >>> >Another Project Euler... (apologies) > >> > > >>> >#73http://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. > >> > > >>> > >> > > >> > >> > > > Note 'Naive solution to PE 73' > >> > > > Generate all the fractions one denominator at a time > >> > > > using low memory. The program exceeds the one > >> > > > minute time requirement even on your new computer. > >> > > > > >> > > > Method: insert a verb into a list of denominators. > >> > > > The verb is necessarily a dyad. y retains the list > >> > > > of unique fractions, x (a scalar) is the next > >> > > > denominator to evaluate. Therefor the verb could be > >> > > > a hook that generates new fractions of one argument > >> > > > which it appends and nubs with the other, producing > >> > > > a "current result". We'll start with a "current > >> > > > result" of 0, removed as a post-processing step. > >> > > > ) > >> > > > > >> > > > Filter=: (#~`)(`:6) > >> > > > odd=: 2&| > >> > > > odd Filter i.5 > >> > > > 1 3 > >> > > > > >> > > > NB. generate the denominators and initial solution of 0 > >> > > > NB. Accumulating the results from few to many decreases > >> > > > NB. the computational work. > >> > > > data=: i.@:(_1x&-) > >> > > > data 8 > >> > > > 8 7 6 5 4 3 2 1 0 > >> > > > > >> > > > numerators=: >.@:-: (] + i.@:-) <.@:(1r3&*) > >> > > > > >> > > > boxdraw_j_ 1 > >> > > > > >> > > > numerators&.> 8 14 > >> > > > +---+-----+ > >> > > > > >> > > > |2 3|4 5 6| > >> > > > +---+-----+ > >> > > > fractions =: %~ numerators > >> > > > > >> > > > ~.@:(, fractions)~/ data 8 > >> > > > 0 1r3 1r4 1r5 2r5 2r7 3r7 3r8 > >> > > > > >> > > > (1r3&< *. <&1r2)Filter ~.@:(, fractions)~/ data 8 > >> > > > 2r5 3r7 3r8 > >> > > > > >> > > > # (1r3&<*.<&1r2)Filter~.@:(, fractions)~/ data 8 > >> > > > 3 > >> > > > > >> > > > > >> > > > NB. watch progress > >> > > > > >> > > > show=: [ smoutput > >> > > > > >> > > > # (1r3&<*.<&1r2)Filter~.@:(, fractions@:show)~/ data 500 > >> > > > > >> > > > > >> > > > > >> ---------------------------------------------------------------------- > >> > > > For information about J forums see > >> http://www.jsoftware.com/forums.htm > >> > > > > >> > > > ---------------------------------------------------------------------- > >> > > For information about J forums see > >> http://www.jsoftware.com/forums.htm > >> > > > >> > ---------------------------------------------------------------------- > >> > For information about J forums see > http://www.jsoftware.com/forums.htm > >> > > >> ---------------------------------------------------------------------- > >> For information about J forums see http://www.jsoftware.com/forums.htm > >> > > > > > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > -- Devon McCormick, CFA ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
