Raul's a clever chap - his trivial is probably my opaque!
That being said, your correspondence has prompted me to reexamine my
own function, which struck _me_ as fairly trivial, and speeded up its
solution sixfold; its solution time is still slightly under quadratic
for n=12000*2^_2 _1 - 1 2 . It's still pretty trivial!
I don't want to be an Euler-spoiler, but perhaps I can say you should
consider whether you need to find the gcf of each pair of numbers.
Good hunting,
Mike
On 16/06/2014 14:13, Jon Hough wrote:
Raul said, "Also, a trivial approach seems plenty adequate here"
I'm curious. How is there a trivial method to solve this problem...
Date: Sun, 15 Jun 2014 18:20:24 -0500
From: [email protected]
To: [email protected]
Subject: Re: [Jprogramming] Project Euler 73
Ooops, I meant
+/12001>".(": f) rplc ' ';',';'r';','
I always have trouble with greater-thans...
Skip
Skip Cave
Cave Consulting LLC
On Sun, Jun 15, 2014 at 4:36 PM, Skip Cave <[email protected]> wrote:
Would this work for Euler 73?
load 'strings'
f =. x:1%2+10000%~i.10001
+/12001<".(": f) rplc ' ';',';'r';','
Skip Cave
Cave Consulting LLC
On Sun, Jun 15, 2014 at 2:39 PM, Mike Day <[email protected]>
wrote:
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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
-----
No virus found in this message.
Checked by AVG - www.avg.com
Version: 2014.0.4592 / Virus Database: 3964/7685 - Release Date: 06/16/14
-----
No virus found in this message.
Checked by AVG - www.avg.com
Version: 2014.0.4592 / Virus Database: 3964/7685 - Release Date: 06/16/14
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
