[Jprogramming] Euler 73

[bill lam]

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

-- 
regards,
====================================================
GPG key 1024D/4434BAB3 2008-08-24
gpg --keyserver subkeys.pgp.net --recv-keys 4434BAB3