▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
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!
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
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
▼
Posts: 2,247
Threads: 200
Joined: Jun 2005
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 sequencesno loops needed.
Namir
Edited: 8 May 2011, 12:02 a.m.
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
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)/30
where
n1 = greatest divisor of 3 <= n;
n2 = greatest divisor of 5 <= n;
n3 = greatest divisor of 15 <= n
if n = 999, then n1 = 999, n2 = 995 and n3 = 990
Regards,
Gerson.
▼
Posts: 1,477
Threads: 71
Joined: Jan 2005
The 12C+ makes this easy. The "brute force" method comes up with the answer in under 7 seconds.
Posts: 260
Threads: 0
Joined: Oct 2008
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 comultiple 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.
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
Here is an HP15C 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 n1.
Example: Find the sum of all the multiples of 3 and 5 up to 180,000.
keystrokes display
180000 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 HP25C or HP33C/E :)
Regards,
Gerson.
▼
Posts: 2,247
Threads: 200
Joined: Jun 2005
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.
▼
Posts: 2,761
Threads: 100
Joined: Jul 2005
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 HP71B, 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.
▼
Posts: 260
Threads: 0
Joined: Oct 2008
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
▼
Posts: 2,247
Threads: 200
Joined: Jun 2005
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
Posts: 79
Threads: 5
Joined: Jun 2007
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.
Posts: 1,545
Threads: 168
Joined: Jul 2005
Why are multiples of 15 included?
They are already totaled by the sum of 3's and the sum of 5's as well.
?
▼
Posts: 3,283
Threads: 104
Joined: Jul 2005
You do not want them to be counted twice.
