FWIW, my solution (called pp for some reason) runs in about 3 seconds
and 0.3MB
1 ts'pp 12000'
3.10239 366720
on a Samsung notebook running 64bit J802 under Windows 8.
It's a pretty simple function involving one implicit loop within one
explicit loop (!?).
It's some years since I solved it. My script shows I was exploring ways
of speeding it up, including use of the Moebius function,
but I seem to have moved on to something else. A promising function
which looks almost correct takes about 0.5 seconds, but uses about 2MB.
Please note that the Euler Project people don't encourage open
discussion of solutions. I don't think I've given too much away here.
Mike
On 15/06/2014 16:59, Jon Hough wrote:
Another Project Euler... (apologies)
#73 http://projecteuler.net/problem=73
I found this one more tricky than it first seems.
My attempt fails.
My reasoning of solution. Trying to find all reduced fractions with denominator
and numerator in range 1... 12000 that are greater than 1/3 but less than
1/2.The most naive way would be to make a 12000x12000 grid of fractions,
nubbing out duplicates. I tried this, and as I expected I ran out of memory.
One problem is duplicates. To get rid of duplicate fractions, for all y <12000,
I only want to check fractions with numerators x (i.e. fractions xry), where x and
y are coprime.(e.g so 1/2 will only be counted once, and not 3/6, 4/8 etc)
My method:
NB. check coprime
coprime =. =&0@:(+/)@:(e.&q:)
NB. get coprimes. (since index starts at zero, and we do not want to compare
with 0 or 1, we start at index 2
NB. and then +2 to get the coprime number.
gcp =. >:@: >:@:I.@: (coprime"(0 0))(}.@:>:@: i.)
e.g. gcp 12 returns 5 7 11.
Next,
NB. get fractions between 1/3 and 1/2
fracs =. +/@:,@:(1r3&<*.1r2&>)@:(%~ func2"0)
If I test for 2 3 4 5 6 7 8 to see how many fractions are between 1/3 and 1/2I
get
fracs >: i.8
3
This is the same value as shown on the question webpage for the value d=8.For d
= 12000if I run the verb, I get an out of memory error.Any ideas how to
proceed? I am wondering if my approach is salvageable, or I need to go back to
the drawing board.
-----
No virus found in this message.
Checked by AVG - www.avg.com
Version: 2014.0.4592 / Virus Database: 3964/7683 - Release Date: 06/15/14
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
