Sum multiples of 3 and 5: Difference between revisions
Content added Content deleted
(8TH version) |
(→{{header|J}}: remove unnecessary complexity -- the using gauss's technique is the right approach here.) |
||
Line 1,874: | Line 1,874: | ||
=={{header|J}}== |
=={{header|J}}== |
||
<lang J> |
|||
mp =: $:~ :(+/ .*) NB. matrix product |
|||
f =: (mp 0 = [: */ 3 5 |/ ])@:i. |
|||
assert 233168 -: f 1000 NB. ****************** THIS IS THE ANSWER FOR 1000 |
|||
</lang> |
|||
For the efficient computation with large n, we start with observation that the sum of these multiples with the reversed list follows a pattern. |
|||
<lang J> |
|||
g =: #~ (0 = [: */ 3 5&(|/)) |
|||
assert 0 3 5 6 9 10 12 15 18 20 21 24 25 27 30 33 35 36 39 40 42 45 48 -: g i. 50 |
|||
assert 48 48 47 46 48 46 47 48 48 47 46 48 46 47 48 48 47 46 48 46 47 48 48 -: (+ |.)g i. 50 NB. the pattern |
|||
assert (f -: -:@:(+/)@:(+|.)@:g@:i.) 50 NB. half sum of the pattern. |
|||
NB. continue... |
|||
</lang> |
|||
Stealing the idea from the python implementation to use 3 simple patterns rather than 1 complicated pattern, |
|||
<lang J> |
|||
first =: 0&{ |
|||
last =: first + skip * <.@:(skip %~ <:@:(1&{) - first) |
|||
skip =: 2&{ |
|||
terms =: >:@:<.@:(skip %~ last - first) |
|||
sum_arithmetic_series =: -:@:(terms * first + last) NB. sum_arithmetic_series FIRST LAST SKIP |
|||
NB. interval is [FIRST, LAST) |
|||
NB. sum_arithmetic_series is more general than required. |
|||
(0,.10 10000 10000000000000000000x)(,"1 0"1 _)3 5 15x NB. demonstration: form input vectors for 10, ten thousand, and 1*10^(many) |
|||
0 10 3 |
|||
0 10 5 |
|||
0 10 15 |
|||
0 10000 3 |
|||
0 10000 5 |
|||
0 10000 15 |
|||
0 10000000000000000000 3 |
|||
0 10000000000000000000 5 |
|||
0 10000000000000000000 15 |
|||
(0,.10 10000 10000000000000000000x)+`-/"1@:(sum_arithmetic_series"1@:(,"1 0"1 _))3 5 15x |
|||
23 23331668 23333333333333333331666666666666666668 |
|||
</lang> |
|||
=== Simple Solution === |
|||
The problem can also be solved with a simple use of inclusion/exclusion; this solution is more in keeping with how one could approach the problem from a more traditional language. |
The problem can also be solved with a simple use of inclusion/exclusion; this solution is more in keeping with how one could approach the problem from a more traditional language. |
||
<lang J> |
<lang J> |