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
