In private correspondence, "Pascal Jasmin" suggests I air these
functions in the forum.
Please note that the following is a spoiler for an Euler Project
solution method, so I'm placing listings some way down.
On my Samsung ultranotebook, that's not ultrafast: (sorry for any
line-wraps)
NB. Yesterday's modified version "pppp" of my old function "pp" used for
a correct Euler submission.
timespacex 'pppp 12000'
0.584461 278400
NB. Today's slightly more complicated version "ppppp"
timespacex 'ppppp 12000'
0.177553 268928
NB. Here's the slower, simpler one, "pppp"
NB. Sorry - it's got two nested loops!!! I'll put an NB. on each line
to help with line-wrapping problems
Both these methods take the 1/3 and 2/3 limits on fractions as given.
pppp =: 3 : 0 NB.
q =. >:i.y NB.
t =. 0 NB.
for_i. }.q}.~(-<.-:y) do. NB. all numerators from 2 to n%2
qp =. y#0 NB. initialise sieve
for_qi. ~. q: i do. NB. loop over nub of prime factors of
numerator
qp =. qp +. y$1{.~-qi NB. set sieve on all products of prime
factors of current numerator
end. NB.
t =. t + +/-. qp#~ (q < 3 * i) * q > 2 * i NB. sum over all
non-products within (1/2, 1/3)
end. NB.
t NB.
)
As I said yesterday, I think it's pretty trivial.
This following version, "ppppp", speeds up even more at the expense of a
bit more complexity, by being more frugal with the sieve.
ppppp =: 3 : 0 NB.
q =. >:i.y NB.
t =. 0 NB.
for_i. }.q}.~(-<.-:y) do. NB.
low =. >: 2 * i NB.
hi =. y <. 3 * i NB.
qp =. 0#~ nq =. 1 + hi - low NB. sieve in interval (1+2i, 3i-1)
for_qi. ~. q: i do. NB.
qp =. qp +. (low-1) }. (low+nq-1)$1{.~-qi NB. offsetting the
ones for prime products
end. NB.
t =. t + +/-. qp NB.
end. NB.
t NB.
)
pppp 12000
7295372
ppppp 12000
7295372
JVERSION
Engine: j701/2011-01-10/11:25
Library: 8.02.09
Qt IDE: 1.1.2/5.3.0
Platform: Win 64
Installer: J802 install
InstallPath: c:/d/j802
More recent Euler problems tend to have much larger N, and methods like
the above often only serve to explore the foothills (or perhaps
molehills) of those puzzles.
Have fun!
Mike
-----
No virus found in this message.
Checked by AVG - www.avg.com
Version: 2014.0.4592 / Virus Database: 3972/7694 - Release Date: 06/17/14
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
