Richard Donovan wrote:
> <: +: *: >: i. 10000
The constraint given at
http://projecteuler.net/index.php?section=problems&id=216 is N>1, so you
probably want 2+i. instead than >:i. .
I haven't given the problem much thought, and I suspect a fast, lean
solution will require mathematical insight rather than programmatic deft,
but I will note that the expression above can be written a number of ways
in J:
t0 =: <:@:+:@:*:@:+&2@:i. NB. Your original
t1 =: _1 0 2&p.@:+&2@:i. NB. Using polynomials (p.)
t2 =: +/\^:2@:({.!.4&7 3) NB. Second derivative of t1
is
4, so...
N =: 1e5
NB. Relative comparison
'5.2d' 8!:2 (%"1 <./) 100 ts&> t0`t1`t2 ,L:0 ' N'
1.95 1.80
1.73 1.20
1.00 1.00
So t2 gets you a factor of 2. As this Forum has recently noted, that's not
terribly exciting. I'm sure there are much better ways to speed up your
verb. One possible avenue to follow is generating primes and testing them
for "t"-ness, rather than generating "t"s and testing them for primality.
First note that you can generate all the primes less than y with
i.&.(_1&p:) y . That leaves the question: given an integer, can we
know if it's a "t"? Well, if we had p.^:_1 we could know whether it was
in the range of _1 0 2&p. . Using the definition of p.^:_1 from
http://www.jsoftware.com/pipermail/programming/2008-October/012314.html :
plt =: i.&.(_1&p:) NB. Primes less than
whole =: = <. NB. The domain of t is
whole numbers
+/@:whole _1 0 2 pI"1 0 plt 100
5
That is, 5 prime numbers less than 100 are "t"s. But, since we don't have
p.^:_1 , and the model I wrote is slow, we can use the inverse of the
original t0 instead.
+/@:whole <:@:+:@:*:@:(+&2)^:_1: plt 100
5
I doubt this approach will scale to 5e7 as required by the challenge.
-Dan
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
