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
