Re: HP15C minichallenge (Project Euler  problem #1) Message #10 Posted by C.Ret on 9 May 2011, 3:51 p.m., in response to message #9 by Gerson W. Barbosa
Quote:
Any explanation?
Yes, of course.
The explanation is really simple.
In the case with only two multiples a and b, the 'Wikipedia Formulae' allow to compute the sum of all multiple bellow m:
a [R/S] add the sum of multiples of a below m, included also the multiples of a.b (simultaneous multiples of a and b) which are a part of the multiples of a.
b [R/S] add the sum of multiples of b below m, included also multiples of a.b (simultaneous multiples of a and b) which are a part of the multiples of b.
As Marcus von Cube explain it, this make the multiples of a and b to be count twice and the resulting sum overestimate the correct sum.
That why we have to correct it by subtracting one time the sum of multiples of a.b by entering
a.b [CHS] [R/S] in the summation process.
When considering three multiples, the same phenomena occur again. But this time, we have to considerer more interactions by correcting the twiced counts of binomial a.b, a.c and b.c multiples as well as full a.b.c multiples.
To resume and making things simplest, let me start from scracht the summation sequence:
a [R/S] add sum of all multiples of a, included binomial a.b and a.c and full a.b.c multiples.
b [R/S] add sum of all multiples of b, included binomial a.b and b.c and full a.b.c multiples.
At this point, we already count a.b and a.b.c twice.
c [R/S] add sum of all multiples of c, included binomial a.c and b.c multiple and trinomial a.b.c multiples.
At this last step, the sum over estimate the correct sum by mistakenly incorporating two times the a.b, a.c and b.c multiples and three times the a.b.c.
To correct this, the next steps are to substrate the binomial multiples :
a.b [CHS] [R/S] which remove one time the twiced counted a.b multiples. But, this also remove the sum of the a.b.c multiples since they are part of the a.b multiples.
At this point, the total overestimate the correct sum by only twiced counting of a.c, b.c and a.b.c multiples.
a.c [CHS] [R/S] which remove one time the twiced counted a.c multiples. But, this also remove again the sum of the a.b.c multiples since they are part of the a.c multiples.
At this point, the total sum overestimate the correct sum by only twiced counting of b.c. So the next step would have been the last one, but it is not the case !
b.c [CHS] [R/S] remove one time the twiced counted b.c multiples. But, this also remove one more time the sum of the a.b.c multiples since they are part of the b.c multiples.
At this point, the current sum is wrong by underestimate the correct answer, because the sum of a.b.c have been remove one time more than needed.
That why we have to ADD the last full multiple counts to the summation, by endind whith:
a.b.c [R/S] which add one time the missing sum of all a.b.c multiples.
At this end point, the resulting sum is the correct sum of all multiples of a , b and c below m.
The same reassignment can be used to compute the sum of a set of four multiples:
+a, +b, +c, +d, ab, ac, ad, bc, bd, cd, +abc, +abd, +acd, +bcd, abcd
Edited: 9 May 2011, 4:35 p.m. after one or more responses were posted
