Well, you can use the fact that 3+6+9+12 is 3*(1+2+3+4) and the fact that the sum of integers is 0.5*n*(n+1) to get something of the form (excluding shared multiples of 15 and excluding 1000 itself):
I understood the logic you suggested but I am not able to understand the Q expression you wrote, specially the use of “k” in the expression/function. Can you please elaborate?
This is problem #1 from https://projecteuler.net
Once you have the correct answer (using any algorithm) you can go to the “thread” for the problem and see how 206 other people have solved it using a variety of languages.
You can also download the the “overview” that discusses an “efficient” solution.
Constant time means the run time of the algorithm does not change, no matter the input size is 1k, 10k or 1M. The sum of the arithmetic sequence takes constant time to calculate using the formula given by @TerryLynch. A fixed number of multiplications and additions are faster than looping 1k, 10k or 1M times.
As you know, q executes from left to right, or better “left of right”.
the “k” in Terry’s functions stores and intermediate value for use later in the execution stream.
Another way of expressing this in q (without the “k” variable) based on the “efficient” solution reported in the Project Euler overview is:
q)f:{floor .5*y*prd 0 1+(x-1) div y}
q){f[x;y]+f[x;z]-f[x;y*z]}[1000;3;5]
233168
q)\ts {f[x;y]+f[x;z]-f[x;y*z]}[100;3;5]
0 2144
q)\ts {f[x;y]+f[x;z]-f[x;y*z]}[100000000;3;5]
0 2144
The \ts reports the time (0 milliseconds) and the space (2144 bytes) used.
The time (0 milliseconds) is “constant” for inputs of 100 and of 100000000. The space is also constant.