It occurs to me that
(1r3) < (NrD) < (1r2)
can be re-written as
(D < 3*N) *. (2*N) < D NB. for N&D>0
On Mon, Oct 10, 2011 at 9:39 AM, Raul Miller <rauldmil...@gmail.com> wrote:
> One approach which should help with efficiency would be to find
> bounding numerators (min and max) for each denominator, and then
> generate the numerators between the bounds and eliminate duplicate
> fractions.
>
> And, if that was too slow, I might be tempted to delve into factoring
> my denominators (for example, when n and 2n are both denominators my
> above approach would be doing duplicate work). But this gets into a
> lot of complexity (and we also have a bound which is arbitrary which
> must be handled here), and complexity has its own computational costs.
>
> --
> Raul
>
> On Mon, Oct 10, 2011 at 8:59 AM, Nick Simicich <simic...@gmail.com> wrote:
> > I looked u faery cycles when I first cracked the forum, then tried
> coding
> > an algorithm. I coded a verb and by the time I got to my fourth or fifth
> > recursin it had slowed. By 10-12 it was painful and I still had a long
> way
> > to go to 12000.
> >
> > In termsof how, the code I posted made rationals of all possible
> numerators
> > and denominators, and counted those that were not reduced when examined.
> I
> > was wondering if it was possible to code that both tacitly and
> efficiently
> > for order 12000
> >
> >
> > On Mon, Oct 10, 2011 at 5:04 AM, Mike Day <mike_liz....@tiscali.co.uk
> >wrote:
> >
> >> I thought I'd check back and see how I solved this: but there's no
> >> trace in my
> >> saved APL or J files, so I suppose I must have done a brute-force
> >> one-liner on
> >> the original, smaller problem.
> >>
> >> So I've just had another look, and today's pretty naive solution works
> >> in about
> >> 2 seconds and about 200 kB on my 2GB laptop; it's order O(n^2), so
> doesn't
> >> scale well, but is fine for the size of problem given.
> >>
> >> (I still think Problem 289, "Eulerian Cycles", is the hardest of the
> lot!
> >> see http://projecteuler.net/problem=289
> >> I haven't yet solved it but I'm _not_ looking for spoilers. Perhaps it
> >> needs what
> >> Crossword Solvers call the PDM, the "Penny Drop Moment." Anyway, that's
> >> another topic.)
> >>
> >> Mike
> >>
> >> On 10/10/2011 12:56 AM, Nick Simicich wrote:
> >> > They increased the program space in Euler 73 to up to 12000 fractions.
> >> > Euler 73 requires that you determine how many exclusive numerators
> and
> >> > denominators there are between 1r3 and 1r2 given that the numerators
> and
> >> > denominators can be up to 12000.
> >> >
> >> > I'm trying to do this in limited space on a 32 bit netbook with not
> too
> >> much
> >> > extra memory, 2 gig total.
> >> >
> >> > Read about it here. http://projecteuler.net/problem=73
> >> >
> >> > The sample space they give is up to 8. This makes it clear that I
> can't
> >> > just say ~. (>:1.8)%8, it has to be more like
> >> >
> >> > #~.(#~ (>&1r3 *.<&1r2)),%/~>:i.8
> >> >
> >> > That works perfectly for 8 and 12, and when you try it with 10000 it
> runs
> >> > out of memory. With 12000 it gives a "limit error". I tried breaking
> the
> >> > problem into smaller tables, and it fails, out of memory when I try to
> >> > combine tables and nub them.
> >> >
> >> > I finally decided I could not keep separate tables, and looked at a 16
> by
> >> 16
> >> > table to get ideas. When I looked at (* (<&1r2 *.>&1r3))%/~>:i.16x I
> >> > didn't see anything, but when I looked at |:(* (<&1r2
> *.>&1r3))%/~>:i.16x
> >> I
> >> > finally realized that any fraction that was reduced would come up
> >> somewhere
> >> > else.
> >> >
> >> > That led to this program:
> >> >
> >> > e73a =: verb define
> >> > count =. 0
> >> > for_i.>:i. x: y do.
> >> > j=.<.i%3x
> >> > count =. count + +/i = {:"_1 ]2 x: (#~ (>&1r3 *.<&1r2))
> >> > i%~j+>:i.((<.i%2x)-j)
> >> > end.
> >> > )
> >> >
> >> > Essentially, I loop over 1<: i<: y where y is 8 or 16 for testing, and
> >> > 12000 for the "final answer"
> >> >
> >> > It builds a vector where the numbers in the vector are all extended
> >> > fractions, and the numerator is between about a third and a half of
> the
> >> > denominator. Then it trims that vector so that the survivors are
> >> greater
> >> > than 1/3 and less than 1/2.
> >> >
> >> > Finally, it looks at the denominators and counts all of the fractions
> >> that
> >> > were not reduced.
> >> >
> >> > I took a couple of half hearted attempts at making it into a one
> >> liner,and I
> >> > could not figure out how to.
> >> >
> >> > What stops me is that, well, I would have to assign the number to a
> >> variable
> >> > before using it in the expression. I could unfactor j and so forth,
> but,
> >> > well, if someone could point me to an online example, or explain, I'd
> >> > appreciate it.
> >> >
> >> > I've seen the item in the forum that applies the method I thought
> about
> >> > using, but they fit it into 32 bits:
> >> >
> >> > $~.;(<@#~>&(%3) *.<&0.5)@:%"0 1/~>:@i.10000
> >> >
> >> > Now
> >> >
> >> > $~.;(<@#~>&(%3) *.<&0.5)@:%"0 1/~>:@i.12000
> >> >
> >> > So far as I see it, well, I didn't understand how the "0 1 part
> worked,
> >> then
> >> > I tried this expression:
> >> >
> >> > ;"0 1/~>:@i.16
> >> >
> >> > So if I wanted to do a lot of unneeded arithmetic, I could rewrite my
> >> deal
> >> > to use this to generate the half of the stuff I didn't care about. But
> >> then
> >> > I'd have to somehow figure out how to put the original denominator
> into
> >> the
> >> > boxes at the head, say. Instead of everything by everything, you only
> get
> >> > n(m max) by 1..m. But it is not at all clear whether that would have
> >> worked
> >> > for me, as I would have had to stash the original denominator or maybe
> >> use
> >> > the greatest denominator, if that worked.
> >> >
> >> >
> >> > -
> >> > Of course I can ride in the carpool lane, officer. Jesus is my
> constant
> >> > companion.
> >> > ----------------------------------------------------------------------
> >> > For information about J forums see
> http://www.jsoftware.com/forums.htm
> >> >
> >>
> >> ----------------------------------------------------------------------
> >> For information about J forums see http://www.jsoftware.com/forums.htm
> >>
> >
> >
> >
> > --
> > Of course I can ride in the carpool lane, officer. Jesus is my constant
> > companion.
> > ----------------------------------------------------------------------
> > 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
^me^ at acm.
org is my
preferred e-mail
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
