The Task:
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.
As often with these kind of riddles, there is a straightforward solution and an elegant, more general one.
Some Thoughts
The problem seems to consist of two steps:
- Finding all multiples of 3 and 5 below 1000,
- Adding them up.
The multiples of 3 below 1000 are 3, 6, 9..., 999. The multiples of 5 are 5, 10, 15, ... 995.
The straightforward way is to calculate the multiples with a simple loop. However, if we use loops, we will have some double entries that are both multiples of 3 and of 5, such as 15, 30, 45. Better idea: We count up all numbers that are divisable by 3 or 5. This way, we will not have any double entries.
The straightforward approach
Let's implement the straightforward way first:
- Define a variable to sum up the results.
(setq *Sum 0)
-
Implement a loop from 1 to 999 (because it should be "below 1000") and add number
whenit is a multiple of 3ora multiple of 5. Multiples can be checked with the modulo function%.If the conditions are fulfilled, our
*Sumvariable should beincreased by the value ofN.
(for N 999
(when
(or
(=0 (% N 3))
(=0 (% N 5)) )
(inc '*Sum N) ) )
- Run!
You can see the full script here.
The smart approach
The solution above works well for small N's, but obviously the larger the numbers are the more expensive it gets.
Now let's have another close look at the equations and think through it again. How about re-shaping the equation like this?
3 + 6 + 9 + 12 + 15 + ... + N =
1*3 + 2*3 + 3*3 + 4*3 + 5*3 + ... + (N/3)*3 =
3 * ( 1 + 2 + 3 + 4 + 5 + ... + N/3)
Note that N/3 is rounded downwards if N can't be divided by 3.
Now we find something interesting: The term 1+2+3+4+5+...+N is also called a triangular number, and luckily, there is an easy equation to calculate the i'th triangular number, which is (n+1)*n/2. So instead of looping from 1 to N, we can simply solve this equation.
Let's try to put this in a general formula. Variables:
-
Nis the number until which we need to count (in the task description: 1000), -
F1is the first multiplicant (in the task description: 3), -
F2is the second multiplicant (in the task description: 5), -
T_{N1}is the{N1}'th triangular number.
So, the sum for one multiplicant F is equal to the T_{N1} * F, where N1=(N-1)/F. ((N-1), because the task description says the upper limit should be below N.) In equations:
N1 = (N-1) / F
Result = F * N1 * (N1 + 1) / 2
Now let's translate this to PicoLisp.
Definition of N1:
(let N1 (/ (dec N) F)
Definition of the result:
(*/ F N1 (inc N1) 2) )
The */ function multiplies all arguments except for the last one, and then divides by the last one.
We put it together in a function definition sumMul with its two arguments N and F:
(de sumMul (N F)
(let N1 (/ (dec N) F)
(*/ F N1 (inc N1) 2) ) )
The return value of the function is its last evaluation, i.e. the last row.
We're almost there, but we need to consider two factors, 3 and 5. If we simply add up the results of both factors, we will have some double entries for the multiples of 15. Therefore we need to subtract those. This is what we get:
(println
(-
(+ (sumMul N 3) (sumMul N 5))
(sumMul N 15) ) )
To check the results also for larger numbers, we could now put the whole function in a loop that increases with decimal power. The result is quite pretty:
23
2318
233168
23331668
2333316668
233333166668
23333331666668
2333333316666668
233333333166666668
23333333331666666668
2333333333316666666668
233333333333166666666668
23333333333331666666666668
2333333333333316666666666668
233333333333333166666666666668
23333333333333331666666666666668
2333333333333333316666666666666668
233333333333333333166666666666666668
23333333333333333331666666666666666668
2333333333333333333316666666666666666668
Note: This problem is also listed on the Rosetta Code Project with solutions in more than 100 programming languages.
The final script can be downloaded here.
Top comments (0)