I continue to try to solve Project Euler problems with J, but you'll
find that it's generally
hard to solve with a naturally APL/J approach. I sometimes lose track
of precision and
resort to Pari/GP.
I think they expect you to use something like the Moebius theorem in
this kind of problem.
Here's a hard-wired solution using that method.
100 (]*2!>:@(<.@%|)) 3 5 _9 15 _25 27 _45
1683 1050 _594 315 _250 162 _135
+/1683 1050 _594 315 _250 162 _135
2231
You find all powers of 3 and of 5 and their products <: 100.
Assign signs according to the sums of parity of their powers,
odd for positive.
Consider 15: 100 <.@% 15 is 6. The triangular number for 6 is
2!7 = 21, so the sum of multiples of 15 is 21*15 is 315.
The assignation of signs deals with the overcounting of certain
multiples.
While this method is way over the top for a problem of this size,
it's almost mandatory for some of the Project's challenges!
Best of luck with them,
Mike
On 05/05/2016 03:35, Geoff Canyon wrote:
So I tried to write code to solve the general case of Project Euler problem
1. The problem given is to find the sum of all the positive integers less
than 1000 that are divisible by 3 or 5. Obviously the specific case is
highly optimizable. But I wanted to solve the general, with any number of
divisors and any upper limit.
So I started by enumerating the integers from 0 to the limit, and finding
the remainder for each list when divided by each of the divisors.
Then I transpose and multiply, so the list is now 0 for each integer
divisible by any of the divisors.
Then I search for 0 in the list, so I end up with 1 for numbers that are
divisible by any of the divisors, and 2 for numbers that aren't.
Then I subtract that list from 1, so divisible numbers are 1, and
non-divisible numbers are 0.
Then I enumerate from 0 to the limit again, and multiply the two lists, so
I have a list with 0 for the numbers that are non-divisible, and the
numbers when they are divisible.
Then I sum that list, and that's the result.
Here's the code. As always, I suck at J, so improvements/suggestions are
welcome.
pe1 =: +/@(([:i.]) * 1&-@(0&i.)@*/"1@|:@(|"0 1 i.))
1 pe1 10 NB. sum of 1..9
45
2 pe1 101 NB. sum of the first 50 even numbers
5050
2 3 5 7 11 13 17 19 23 29 pe1 1000 NB. difficult to do the "optimized" way
305863
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
