HP-15C mini-challenge (Project Euler - problem #1) « Next Oldest | Next Newest »

 ▼ Gerson W. Barbosa Posting Freak Posts: 2,761 Threads: 100 Joined: Jul 2005 05-07-2011, 08:00 PM 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! ▼ Gerson W. Barbosa Posting Freak Posts: 2,761 Threads: 100 Joined: Jul 2005 05-07-2011, 11:00 PM 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...) ▼ Namir Posting Freak Posts: 2,247 Threads: 200 Joined: Jun 2005 05-07-2011, 11:54 PM 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. ▼ Gerson W. Barbosa Posting Freak Posts: 2,761 Threads: 100 Joined: Jul 2005 05-08-2011, 12:14 AM 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. ▼ Katie Wasserman Posting Freak Posts: 1,477 Threads: 71 Joined: Jan 2005 05-08-2011, 09:23 AM The 12C+ makes this easy. The "brute force" method comes up with the answer in under 7 seconds. C.Ret Senior Member Posts: 260 Threads: 0 Joined: Oct 2008 05-08-2011, 04:13 PM 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. ▼ Gerson W. Barbosa Posting Freak Posts: 2,761 Threads: 100 Joined: Jul 2005 05-08-2011, 08:36 PM 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. ▼ Namir Posting Freak Posts: 2,247 Threads: 200 Joined: Jun 2005 05-09-2011, 12:06 PM 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. ▼ Gerson W. Barbosa Posting Freak Posts: 2,761 Threads: 100 Joined: Jul 2005 05-09-2011, 02:18 PM 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. ▼ C.Ret Senior Member Posts: 260 Threads: 0 Joined: Oct 2008 05-09-2011, 03:51 PM 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 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 ▼ Namir Posting Freak Posts: 2,247 Threads: 200 Joined: Jun 2005 05-09-2011, 04:05 PM 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 ▼ Gerson W. Barbosa Posting Freak Posts: 2,761 Threads: 100 Joined: Jul 2005 05-09-2011, 06:30 PM 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: Paul Guertin Member Posts: 79 Threads: 5 Joined: Jun 2007 05-09-2011, 08:32 PM 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. Gene Wright Posting Freak Posts: 1,545 Threads: 168 Joined: Jul 2005 05-08-2011, 08:58 AM Why are multiples of 15 included? They are already totaled by the sum of 3's and the sum of 5's as well. ? ▼ Marcus von Cube, Germany Posting Freak Posts: 3,283 Threads: 104 Joined: Jul 2005 05-08-2011, 11:08 AM You do not want them to be counted twice.

 Possibly Related Threads... Thread Author Replies Views Last Post FRAM71 Project aj04062 1 459 11-25-2013, 01:59 PM Last Post: Hans Brueggemann Euler's Constant Approximation Namir 0 310 10-19-2013, 11:32 AM Last Post: Namir [HP-PRIME] QPI project CompSystems 0 291 10-09-2013, 02:51 PM Last Post: CompSystems HPCC Mini Conference 2013 hugh steers 6 763 09-13-2013, 04:27 PM Last Post: BruceH RPN-1200 Project Benoit Maag 0 305 08-25-2013, 01:05 AM Last Post: Benoit Maag Picture from the Mini-HHC (LA) Geir Isene 11 1,076 07-07-2013, 01:06 PM Last Post: Jim Horn My birthday, so a little commemorative mini-challenge ! Valentin Albillo 43 3,393 03-07-2013, 03:44 AM Last Post: Walter B WP 34S mini-challenge (B) Gerson W. Barbosa 17 1,458 12-27-2012, 04:39 PM Last Post: Marcus von Cube, Germany What do you think of this project??? Pierre 1 414 11-21-2012, 06:58 PM Last Post: Eddie W. Shore TI 2550III project, help me I can help you. watchdoctor 2 444 10-19-2012, 10:13 PM Last Post: Joerg Woerner

Forum Jump: 