I confess to finding a slow & exhaustive but correct solution
in PARI-GP, with thanks to John for pointing the package
out to me a while ago. I didn't wait to find an elegant method
in J or otherwise.
FWIW, I probed the logic of another recent Euler problem
(208) in Dyalog APL, but that didn't provide sufficient precision,
and I had to go to J for the final solution.
J APL etc are great for exploring these problems. Scaling up
is sometimes a significant extra problem.
Mike
John Randall wrote:
Richard Donovan wrote:
Is anyone working on this problem?
Yes: I solved it in J.
I tried:
+/ 1 p: <: +: *: >: i. 10000
2202
To confirm the algorithm was working for n <: 10,000
But the actual problem is for n <: 50,000,000 and my algorithm
only works as far as 30,000 before taking excessive time.
If you are going to test every number for primality, you should use the
Miller-Rabin test from
http://www.jsoftware.com/jwiki/Essays/Primality_Tests
However, this will still take a long time in any language.
The problem can actually be solved using no explicit primality testing at
all. I can write a Java program using this algorithm that runs in a few
seconds, but adapting it to J is still too long.
I ended up using a mixed strategy, with some shortcuts based on the
behavior of the sequence being tested, and some primality testing. I was
not completely happy with the result, but it was within reason.
Best wishes,
John
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
------------------------------------------------------------------------
No virus found in this incoming message.
Checked by AVG - http://www.avg.com
Version: 8.0.175 / Virus Database: 270.9.4/1793 - Release Date: 16/11/2008 19:58
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
