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 HP-15C (or HP-11C) in 30 seconds or less. Have fun!
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 HP-15C is not a good tool here (at least the ordinary 15C...)
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 +
sum of 5 and multiples in range 5 to 999 -
sum of 15 and multiples in range 15 to 999
I calculate each sum using the same basic approach Gauss used to calculate the sum of integer sequences--no loops needed.
Namir
Edited: 8 May 2011, 12:02 a.m.
Quote:
I calculate each sum using the same basic approach Gauss used to calculate the sum of integer sequences.
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)/30where
n1 = greatest divisor of 3 <= n;
n2 = greatest divisor of 5 <= n;
n3 = greatest divisor of 15 <= nif n = 999, then n1 = 999, n2 = 995 and n3 = 990
Regards,
Gerson.
Why are multiples of 15 included?
They are already totaled by the sum of 3's and the sum of 5's as well.
?
The 12C+ makes this easy. The "brute force" method comes up with the answer in under 7 seconds.
You do not want them to be counted twice.
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
02 "UPPER LIM
03 PROMPT @ User enter upper limit (ie 999)
04 1
05 - @ may have a DSE X spare a prgm step here ?
06 STO 00
07 0 @ init Total SUM
08 LBL 01 @ HP display current sum of multiple
09 STOP @ User enter next multiple to add (+k)
Or to substract (-k)
10 RCL 00
11 RCL Y
12 ABS @ throw sign away !
13 /
14 INT @ for positive numbers, IP or INT is FLOOR (not CEIL)
15 *
16 LastX
17 1
18 +
19 *
20 2
21 / @ compute SUM_k
22 + @ add or substratc it to Total
23 GTO 01
Usage:
EXQ “EULER
Enter upper limit : 1000 and press [R/S]
Enter first multiple to add in sum : +3 and press [R/S]
The calculator display intermediate summation: 166833
Enter second multiple to add in sum : +5 and press [R/S]
The calculator display intermediate summation: 266333.
Enter co-multiple to subtract from sum : 15 [CHS] and press [R/S]
The calculator display expected result: 233168.
Note that it is so easy to get the sum from the 10000 first integers or 500000 as well sum of other multiple.
For example: To find the sum of all the multiples of 3, 5 or 7 below 10000.
EXQ “EULER
ENTER: 1 [EEX] 4 press [R/S]
Calculator display 0.0000
ENTER: 3 press [R/S], the calculator display intermediate summation: 16668333.
ENTER: 5 press [R/S], intermediate sum: 26663333.
ENTER: 7 press [R/S], intermediate display : 33805475.
ENTER: 15 [CHS] [R/S], intermediate corrected sum: 30473810.
ENTER: 21 [CHS] [R/S], intermediate corrected sum: 28089764.
ENTER: 35 [CHS] [R/S], intermediate corrected sum: 26663339.
ENTER: 105 [CHS][CHS] [R/S], note that this last (double)-multiple have to be add, not substract from the current sum.
The calculator display expected sum of all the multiples of 3, 5 or 7 below 1000 : 27142139.
P.S.:
An alternative version for HP41, using stack manipulation and no register:
01 LBL 'EULER @ user enter upper limit (ie 1000) in x:
02 DSE X
03 0
04 LBL 01 @ upper lim in y: and current sum in x:
05 STOP
06 RCL Z
07 X<->Y
08 ST/ Y
09 x<->y
10 ABS
11 INT
12 *
13 LASTX
14 ISG X
15 SF 00 @ any operation there, always skipped
16 *
17 2
18 /
19 +
20 GTO 01
Edited: 8 May 2011, 4:56 p.m.
Here is an HP-15C version of your short and versatile program:
001- f LBL B
002- STO 0
003- 0
004- f LBL 6
005- R/S
006- RCL 0
007- x<>y
008- /
009- g LSTx
010- x<>y
011- g ABS
012- g INT
013- *
014- g LSTx
015- 1
016- +
017- *
018- 2
019- /
020- +
021- GTO 6
Usage is the same, except that it now sums up to n, not to n-1.
Example: Find the sum of all the multiples of 3 and 5 up to 180,000.
keystrokes display180000 GSB B 0.000000000
3 R/S 5,400,090,000.
5 R/S 8,640,180,000.
15 CHS R/S 7,560,090,000.
I'd written a generalized program myself (n>14), only to discover the formula at wikipedia would allow for a faster and shorter program. Anyway, here it is:
001- f LBL A 019- g x=0 037- + 055- + 073- f LBL 2
002- STO 0 020- g GSB 2 038- g LSTx 056- g LSTx 074- g F?2
003- 0 021- RCL 0 039- * 057- * 075- g RTN
004- STO 4 022- 1 040- 6 058- 3 076- RCL 0
005- g CF 1 023- 5 041- / 059- 0 077- STO 2
006- g CF 2 024- / 042- STO 5 060- / 078- 1
007- g CF 3 025- f FRAC 043- 5 061- STO+ 5 079- STO+ 4
008- f LBL 0 026- g x=0 044- RCL 2 062- RCL 5 080- g SF 2
009- RCL 0 027- g GSB 3 045- + 063- g RTN 081- g RTN
010- 3 028- 3 046- g LSTx 064- f LBL 1 082- f LBL 3
011- / 029- RCL 4 047- * 065- g F?1 083- g F?3
012- f FRAC 030- g TEST 5 @ (x=y) 048- 1 066- g RTN 084- g RTN
013- g x=0 031- GTO 4 049- 0 067- RCL 0 085- RCL 0
014- GSB 1 032- f DSE 0 050- / 068- STO 1 086- STO 3
015- RCL 0 033- GTO 0 051- STO+ 5 069- 1 087- 1
016- 5 034- f LBL 4 052- 1 070- STO+ 4 088- STO+ 4
017- / 035- 3 053- 5 071- g SF 1 089- g SF 3
018- f FRAC 036- RCL 1 054- RCL 3 072- g RTN 090- g RTN
Example:
180,000 GSB A -> 7,560,090,000. ( ~ 8 seconds)999 GSB A -> 233,168.0000 ( ~ 29 seconds)
Perhaps someone would be willing to use the formula in the wikipedia article. It might well fit in the HP-25C or HP-33C/E :-)
Regards,
Gerson.
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) -
{ sum_15(1000) + sum_21(1000) + sum_35(1000) + sum_105(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.
Quote:
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) -
{ sum_15(1000) + sum_21(1000) + sum_35(1000) + sum_105(1000) }
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) -
{ sum_15(1000) + sum_21(1000) + sum_35(1000) }
Using C.Ret's program, which uses the Wikipedia formula, I get
1000 GSB B 0.000000000
3 R/S 166,833.0000.
5 R/S 267,333.0000.
7 R/S 338,404.0000.
15 CHS R/S 305,239.0000.
21 CHS R/S 281,551.0000.
35 CHR R/S 267,341.0000.
105 R/S 272,066.0000.
That's what I get on the HP-71B, using the brute force program:
10 DESTROY ALL
20 T=0
30 FOR N=1 TO 1000
40 IF MOD(N,3)=0 OR MOD(N,5)=0 OR MOD(N,7)=0 THEN T=T+N
50 NEXT N
60 DISP T
>run
272066
Any explanation?
Regards,
Gerson.
Edited: 9 May 2011, 2:25 p.m.
Quote:Yes, of course.
Any explanation?
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 over-estimate 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 under-estimate 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
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
Quote:
Very good explanation!!!
Agreed!
Quote:
...famous French mathematicians in the 18th or 19th century (like Fourier, Hermite, Lagrange, or Laguerre)
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://www-groups.dcs.st-andrews.ac.uk/~history/BirthplaceMaps/France.html
http://www-groups.dcs.st-andrews.ac.uk/~history/BirthplaceMaps/Germany.html
http://www-groups.dcs.st-andrews.ac.uk/~history/BirthplaceMaps/UK.html
http://www-groups.dcs.st-andrews.ac.uk/~history/BirthplaceMaps/Italy.html
http://www-groups.dcs.st-andrews.ac.uk/~history/BirthplaceMaps/Spain.html
Also look up "Principle of Inclusion-Exclusion" (often abbreviated PIE). See for instance this page on the Art of Problem Solving wiki. This is a standard tool in combinatorics.