HP15C minichallenge (Project Euler  problem #1)  Printable Version + HP Forums (https://archived.hpcalc.org/museumforum) + Forum: HP Museum Forums (https://archived.hpcalc.org/museumforum/forum1.html) + Forum: Old HP Forum Archives (https://archived.hpcalc.org/museumforum/forum2.html) + Thread: HP15C minichallenge (Project Euler  problem #1) (/thread183803.html) 
HP15C minichallenge (Project Euler  problem #1)  Gerson W. Barbosa  05072011 The first Project Euler problem is 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. The challenge is to solve this one on the HP15C (or HP11C) in 30 seconds or less. Have fun!
Re: HP15C minichallenge (Project Euler  problem #1)  Gerson W. Barbosa  05072011 Forget about it! My solution uses essentially the same formula in the reference article and is not as fast as it could be. Other interesting problems in the list, but I fear the HP15C is not a good tool here (at least the ordinary 15C...)
http://projecteuler.net/index.php?section=problems
Re: HP15C minichallenge (Project Euler  problem #1)  Namir  05072011 Bummer! I was working on a solution that does NOT uses loops. The sum we seek is:
sum = sum of 3 and multiples in range 3 to 999 + I calculate each sum using the same basic approach Gauss used to calculate the sum of integer sequencesno loops needed. Namir
Edited: 8 May 2011, 12:02 a.m.
Re: HP15C minichallenge (Project Euler  problem #1)  Gerson W. Barbosa  05082011 Quote: Yes, I remembered Gauss's approach too but was not clever enough to find a formula in terms of n only (and not to notice the one in my own reference was better :)
S = n1*(n1 + 3)/6 + n2*(n2 + 5)/10  n3(n3 + 15)/30 Regards, Gerson.
Re: HP15C minichallenge (Project Euler  problem #1)  Gene Wright  05082011 Why are multiples of 15 included? They are already totaled by the sum of 3's and the sum of 5's as well. ?
Re: HP15C minichallenge (Project Euler  problem #1)  Katie Wasserman  05082011 The 12C+ makes this easy. The "brute force" method comes up with the answer in under 7 seconds.
Re: HP15C minichallenge (Project Euler  problem #1)  Marcus von Cube, Germany  05082011 You do not want them to be counted twice.
Re: HP15C minichallenge (Project Euler  problem #1)  C.Ret  05082011 Thank you for the formulae. At first glance, I was surprise by the divisor (6, 10 and 30), since using my own production I use the multiplier 3x, 5x and 15x, not the divisor, until I realise that what you use k and n the opposite way I used ! I also have trouble with the limit, here 1000. Due to the example give for natural integers below 10, we have to understand that we have to consider only integer strictly below 1000. This makes a difference, since 1000 is a multiple of 5. 999/3 is 333, we have 333 multiples of 3 from in the set (from 0 to 1000 exclude). The sum of all these multiple of 3 is SUM_3 = 3x(333.(333+1))/2 999/5 is 199.8, we have 199 multiples of 5 in the set. The sum of all these multiple is SUM_5 = 5x(199.200)/2 999/15 is 66.6, we have 66 multiples of 15 in the set. The sum of all these multiple of both 3 and 5 have to be substrated from the total, to avoid twiced counts. That why I put a minus sign in from of it : SUM_15 = 15x(66.(66+1))/2 = 33165 Here is the time to generalize the method: Since I have no HP15C at hand, here is a cool code for HP41C, reader of this forum main easely convert it or adpted it for an HP15C.
01 * LBL "EULER
Usage:
Note that it is so easy to get the sum from the 10000 first integers or 500000 as well sum of other multiple.
EXQ “EULER
P.S.: 01 LBL 'EULER @ user enter upper limit (ie 1000) in x: Edited: 8 May 2011, 4:56 p.m.
Re: HP15C minichallenge (Project Euler  problem #1)  Gerson W. Barbosa  05082011 Here is an HP15C version of your short and versatile program:
001 f LBL B Usage is the same, except that it now sums up to n, not to n1.
Example: Find the sum of all the multiples of 3 and 5 up to 180,000. keystrokes display
001 f LBL A 019 g x=0 037 + 055 + 073 f LBL 2
Example: 180,000 GSB A > 7,560,090,000. ( ~ 8 seconds)
Regards, Gerson.
Re: HP15C minichallenge (Project Euler  problem #1)  Namir  05092011 If we "upgrade" the problem to say calculate the sum of all numbers up to 1000 that are multiples of 3, 5, AND 7, does it complicate matters greatly or can we use the Wikipedia functions as follows:
Sum = sum_3(1000) + sum_5(1000) + sum_7(1000)  In calculating sum_105(1000) will there be duplicates with sum_15(1000), sum_21(1000), and sum_35(1000)? If we expand the set of numbers further to be multiples of 3, 5, 7, and 11, things get more complicated, making a solution that uses a loop easier to implement albeit at the cost of additional CPU time.
Namir Edited: 9 May 2011, 12:09 p.m.
Re: HP15C minichallenge (Project Euler  problem #1)  Gerson W. Barbosa  05092011 Quote: Namir, That's what I would have done myself too. It appears, however, the correct formula is
Sum = sum_3(1000) + sum_5(1000) + sum_7(1000) + sum_105(1000)  Using C.Ret's program, which uses the Wikipedia formula, I get
1000 GSB B 0.000000000 That's what I get on the HP71B, using the brute force program:
10 DESTROY ALL Any explanation? Regards, Gerson.
Edited: 9 May 2011, 2:25 p.m.
Re: HP15C minichallenge (Project Euler  problem #1)  C.Ret  05092011 Quote: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. 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.
c [R/S] add sum of all multiples of c, included binomial a.c and b.c multiple and trinomial a.b.c 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.
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.
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. 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:
Edited: 9 May 2011, 4:35 p.m. after one or more responses were posted
Re: HP15C minichallenge (Project Euler  problem #1)  Namir  05092011 I will not be surprised if one of the famous French mathematicians in the 18th or 19th century (like Fourier, Hermite, Lagrange, or Laguerre) was your great great great grandfather!!! Very good explanation!!! :)
Namir
Re: HP15C minichallenge (Project Euler  problem #1)  Gerson W. Barbosa  05092011 Quote: Agreed!
Quote: By the way I've always wondered why some countries have been home to a large number of great mathematicians and some have not. Bad weather conditions? (Too cold to play outside, better staying at home and studying :). I may be wrong, but in the maps below the densities get lower as climates get warmer:
http://wwwgroups.dcs.standrews.ac.uk/~history/BirthplaceMaps/Germany.html http://wwwgroups.dcs.standrews.ac.uk/~history/BirthplaceMaps/UK.html http://wwwgroups.dcs.standrews.ac.uk/~history/BirthplaceMaps/Italy.html
http://wwwgroups.dcs.standrews.ac.uk/~history/BirthplaceMaps/Spain.html
Re: HP15C minichallenge (Project Euler  problem #1)  Paul Guertin  05092011 Also look up "Principle of InclusionExclusion" (often abbreviated PIE). See for instance this page on the Art of Problem Solving wiki. This is a standard tool in combinatorics.
