You could try figuring, for each possible denominator: the possible numerators; make rationals of them; discard any that weren't in lowest terms. Or, just keep the count of how many there were. Then add em up.
Henry Rich On 10/9/2011 8:20 PM, bill lam wrote: > The problem stated that n and d are relative prime, does it help? I don't > think those problems require or encourage brute force solution. > > ps. I forgot my account password and cannot recall how to solve it. > > Вск, 09 Окт 2011, Nick Simicich писал(а): >> 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
