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
