the matrix computed by 1=+./~>:i.12000 should give all possible combination of relative prime albeit it is a brute force method.
Вск, 09 Окт 2011, Henry Rich писал(а): > 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 -- regards, ==================================================== GPG key 1024D/4434BAB3 2008-08-24 gpg --keyserver subkeys.pgp.net --recv-keys 4434BAB3 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
