On 15/06/2014 16:59, Jon Hough wrote:
>Another Project Euler... (apologies)
>#73http://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.
Note 'Naive solution to PE 73'
Generate all the fractions one denominator at a time
using low memory. The program exceeds the one
minute time requirement even on your new computer.
Method: insert a verb into a list of denominators.
The verb is necessarily a dyad. y retains the list
of unique fractions, x (a scalar) is the next
denominator to evaluate. Therefor the verb could be
a hook that generates new fractions of one argument
which it appends and nubs with the other, producing
a "current result". We'll start with a "current
result" of 0, removed as a post-processing step.
)
Filter=: (#~`)(`:6)
odd=: 2&|
odd Filter i.5
1 3
NB. generate the denominators and initial solution of 0
NB. Accumulating the results from few to many decreases
NB. the computational work.
data=: i.@:(_1x&-)
data 8
8 7 6 5 4 3 2 1 0
numerators=: >.@:-: (] + i.@:-) <.@:(1r3&*)
boxdraw_j_ 1
numerators&.> 8 14
+---+-----+
|2 3|4 5 6|
+---+-----+
fractions =: %~ numerators
~.@:(, fractions)~/ data 8
0 1r3 1r4 1r5 2r5 2r7 3r7 3r8
(1r3&< *. <&1r2)Filter ~.@:(, fractions)~/ data 8
2r5 3r7 3r8
# (1r3&<*.<&1r2)Filter~.@:(, fractions)~/ data 8
3
NB. watch progress
show=: [ smoutput
# (1r3&<*.<&1r2)Filter~.@:(, fractions@:show)~/ data 500
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
