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...)

http://projecteuler.net/index.php?section=problems

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)/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.

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               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 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:

---

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.