The Museum of HP Calculators

HP Forum Archive 20

 A new 6-problem challenge (free42 or 42s)Message #1 Posted by Allen on 10 June 2011, 5:18 p.m. Thanks to Gerson for introducing the Project Euler a few weeks back on the msg board. There are so many fun programming nuggets in there. I've been reading through several of the problems, and many are quite conducive to programming on the HP 42S or similar machine. How about a challenge? Guidelines: 1. Goal is to program euler.net problems: 1,2,3,4,5,and 6 using a HP 42s (free42 or similar). If you use a 32S(II) that's OK too, but harder. 2. All programs must start with a LBL, but do not have to contain a RTN statement. (e.g. byte counts can be done with only one program at a time in memory) 3. Brute force is allowed, but boring. 4. Number entry: Programs may accept no more than 1 integer value from the user. Any further data entry must be built in to the program. For example in problem 2 if you are looping to 4e6, you can enter 4e6 and press R/S, but you can't enter two or three stack values as inputs. e.g. the first three terms of Fibonacci series 1,2,3,...) 5. Initial Scoring is the sum of the byte count for the problems 1-6. > 240 : Beginner 230-220 : Advanced 220-210 : Very Good! 210-200 : Black Belt!! < 200 : Grand Master 6. Bonus round is problem 28 subtract 1 byte from the total above for every byte under 25 bytes used for problem 28. For example a 23 byte solution to p.28 gets a 2 byte subtraction from the total above) 7. Optimize first for byte size then for lines of code. (if two programs of the same size, the one with fewest lines of code is supreme). 8. No googling solutions. I'm sure there are some posted outside the Euler.net portal, but copying others' work takes the fun out. Any one interested? Edited: 10 June 2011, 5:58 p.m.

 Re: A new 6-problem challenge (free42 or 42s)Message #2 Posted by Jim Horn on 10 June 2011, 6:53 p.m.,in response to message #1 by Allen The optional problem is easy in closed form - 21 bytes, counting the label. An input of pi gives about 28.294 if that means anything. I'm curious how this approach can be tweaked to be smaller.

 Re: A new 6-problem challenge (free42 or 42s)Message #3 Posted by Allen on 10 June 2011, 8:37 p.m.,in response to message #2 by Jim Horn Jim, Fast work coming up with the closed form! Mine is 20 bytes of the form: (x(x(ax+b)+c)+d)/e (numbers omitted to avoid spoilers), same result as you when PI is entered. I'll bet I'm saving that extra byte by filling up the stack and using a series of a * b + * c + *.. etc. I have a loop version at 21 bytes, 20 bytes closed form but can't get either any smaller. Tip: If you already have a closed-form equation type it into Wolfram Alpha.. One of the "alternate forms" should be calculator friendly. Example: http://www.wolframalpha.com/input/?i=x^2%2B6*x%2B6 Edited: 10 June 2011, 8:38 p.m.

 Re: A new 6-problem challenge (free42 or 42s)Message #4 Posted by Gerson W. Barbosa on 11 June 2011, 1:16 a.m.,in response to message #3 by Allen No spoiler as this will require at least 40 bytes. You're right, Horner should be the next step. n(n+1)+(n-1){2(n-1)[(n-1)/3+1]+(1-n)/2+4/3}-1 ------- 25 bytes, one-letter label 28.2944435257 when n=pi Edited: 11 June 2011, 1:31 a.m.

 Re: A new 6-problem challenge (free42 or 42s)Message #5 Posted by Gerson W. Barbosa on 11 June 2011, 3:22 a.m.,in response to message #4 by Gerson W. Barbosa Some explanation: 43 44 45 46 47 48 49 42 21 22 23 24 25 26 41 20 7 8 9 10 27 40 19 6 1 2 11 28 39 18 5 4 3 12 29 38 17 16 15 14 13 30 37 36 35 34 33 32 31 Pattern of half-diagonals, clock-wise: 3^2, 5^2, 7^2, ... 2^2-1, 4^2-3, 6^2-5, ... 2^2+1, 4^2+1, 6^2+1, ... 3^2-2, 5^2-4, 7^2-6, ... These add up to 2(2^2 + 3^2 + 4^2 + ... + n^2) - (1 + 2 + 3 + ... + n-1 ) + (n - 1)/2 + 1 or 2(1^2 + 2^2 + 3^2 + 4^2 + ... + n^2) - (1 + 2 + 3 + ... + n-1 ) + (n - 1)/2 - 1 = 2*Sum(n=1,n,n^2) - Sum(n=1,n-1,n) + (n - 1)/2 = 2*Sum(n=1,n,n^2) - T(n-1) + (n -1)/2 where T(n-1) is the nth number, Since T(n) = n/2*(n+1) then T(n-1) = n*(n-1)/2 Now we need only compute the sum of the squares. Let's do it for n up to 5 first, as an example: 1^2 + 2^2 + 3^2 + 4^2 + 5^2, which we can rewrite as 1 3 6 10 15 _________________ | 1 + 1 + 1 + 1 + 1 + | 10 | 2 + 2 + 2 + 2 + 1 + | 6 | 3 + 3 + 3 + 2 + 1 + | 3 | 4 + 4 + 3 + 2 + 1 + | 1 | 5 + 4 + 3 + 2 + 1 | When summing the elements diagonally, as indicated, we get 1^2 + 2^2 + 3^2 + 4^2 + 5^2 = 15 + 2*(1 + 3 + 6 + 10) = 5, that is T(5) + 2*Sum(n=1,4,T(n)) Generalizing, Sum(1,n,n^2) = T(n) + 2*Sum(n=1,n-1,T(n)) T(n) = n/2*(n+1), as we know, but an expression for the sum T(n), for n=1 up to n, is still lacking. I won't derive it here (done it once long ago, don't remember the details), but I'll try to find an expression empirically, given that 1/6 is one factor in the expression (all I remember). Let's write a small table to help us: n 1 2 3 4 5 6 T(n) 1 3 6 10 15 21 Sum(T(n)) 1 4 10 20 35 56 6*S(Tn)/T(n) 6 8 10 12 14 16 , that is, 2*n+4 Then we can write Sum(n=1,n-1,T(n)) = 1/6*(2n + 4)*n/2*(n+1) = 1/6*((n-1)^3 + 3(n-1)^2 + 2(n-1)) Now we the expression we are looking for can be completed: S = 2*Sum(n=1,n,n^2) - Sum(n=11,n-1,n) + (n - 1)/2 - 1 S = 2*(T(n) + 2*Sum(n=1,n-1,T(n))) - Sum(n=1,n-1,n) + (n - 1)/2 - 1 S = 2*(n/2*(n+1) + 2*1/6*((n-1)^3 + 3(n-1)^2 + 2(n-1))) - n*(n-1)/2 + (n - 1)/2 - 1 A little algebra yields S = n*(n + 1) + (n - 1)*(2*(n - 1)*((n - 1)/3 + 1) + (1 - n)/2 + 4/3) - 1 Further optimization is required, like applying a Horner scheme to take advantage of the RPN stack. Edited: 11 June 2011, 3:25 a.m.

 Bonus problem and horner methodMessage #6 Posted by Allen on 11 June 2011, 8:43 a.m.,in response to message #5 by Gerson W. Barbosa Gerson, Nice work! A quick check in W|A shows the horner methods match. I like your explanation.. http://www.wolframalpha.com/input/?i=n*%28n+%2B+1%29+%2B+%28n+-+1%29*%282*%28n+-+1%29*%28%28n+-+1%29%2F3+%2B+1%29+%2B+%281+-+n%29%2F2+%2B+4%2F3%29+-+1 While the end is the same I approached the problem more like a cinnamon roll. Unroll each ring individually and you can see the pattern: Ring Sum ------------------------------------------------------------------- Core: 1 1 = 4(1) -3 *-> <-* <-- 5 + 7 = 2(6) Row 1: 3 4 5 6 7 8 9 *-------> <-------* 3 + 5 = 2(6) *-----> <----* 17 + 21 = 2(19) Row 2: 13 14 15 16 17 18 19 20 21 22 23 24 25 *-----------------> <----------------* 13 + 25 = 2(19) * indicates a corner So one must sum over a a closed-form formula F(n) for 1,6,19,40... Multiply by 4 and subtract 3 for the core:

 Re: Bonus problem and horner methodMessage #7 Posted by Gerson W. Barbosa on 11 June 2011, 2:55 p.m.,in response to message #6 by Allen Quote:So one must sum over a a closed-form formula F(n) for 1,6,19,40... Multiply by 4 and subtract 3 for the core: Nice approach! A closed-form formula for F(n) is F(n) = 4*(n\2+1)^2 - 7*(n\2 + 1) + 4 or F(n) = (2*n^2 - 3*n + 3)/2 Regards, Gerson. Edited: 11 June 2011, 3:23 p.m.

 Re: Bonus problem and horner methodMessage #8 Posted by Thomas Klemm on 13 June 2011, 3:18 p.m.,in response to message #7 by Gerson W. Barbosa When in need of a closed-form formula for a polynomial sequence consider the following approach using the difference-operator D f(n) := f(n+1) - f(n): n: 0 1 2 3 4 ... f(n): 1 25 101 261 537 ... D f(n): 24 76 160 276 ... D2 f(n): 52 84 116 ... D3 f(n): 32 32 ... With $C(n,k)=\binom{n}{k}$ you can write down the result immediately: f(n) = 1 C(n,0) + 24 C(n,1) + 52 C(n,2) + 32 C(n,3) or $f(n)=1+24n+52\frac{n(n-1)}{1\cdot2}+32\frac{n(n-1)(n-2)}{1\cdot2\cdot3}$ Using the Horner-like schema the expression can be rewritten to: $f(n)=((32\frac{n-2}{3}+52)\frac{n-1}{2}+24)n+1$ Plug that expression into WolframAlpha to get: $\frac{16n^3}{3}+10n^2+\frac{26n}{3}+1$ This is in accordance with what you find at the on-line encyclopedia of integer sequences. Cheers Thomas Explanation: $f(n)=\sum_{k=0}^{m}a_k\cdot C(n,k)$ D C(n,k) = C(n+1,k) - C(n,k) = C(n,k-1) Di C(n,k) = C(n,k-i) $D^{i}f(n)=\sum_{k=0}^{m}a_k\cdot C(n,k-i)$ C(n,0) = 1 for all n => C(0,0) = 1 C(0,k) = 0 for all k > 0 $D^{i}f(n)\mid_{n=0}=a_i$ Edited: 14 June 2011, 1:20 a.m. after one or more responses were posted

 Re: Bonus problem and horner methodMessage #9 Posted by Allen on 13 June 2011, 8:46 p.m.,in response to message #8 by Thomas Klemm Thank you! I never thought about using the Difference function to reverse out the polynomial coefficients. Very clever. I agree with you assessments on the byte count above- very impressive. I did not know what the minimum goal should be as I had only myself finished the rough draft of each code before posting the challenge. I later achieved some economy of 5-10 bytes, but mine would require significant rewrites and change of approach to get below your solution to puzzle 1 and 3. Very well done indeed! FWIW, I had also considered an 18- byte version of puzzle 18 which pre-loaded 2N into the Stat registers and the summed over N with 4N on the X and Y stack. My adding RCL11 and RCL14 one could get sum(16N^2+4N)+4N+1. At 22+ bytes that's easy, much harder once you get below 18.

 Re: Bonus problem and horner methodMessage #10 Posted by Thomas Klemm on 14 June 2011, 2:08 a.m.,in response to message #9 by Allen Quote: I never thought about using the Difference function to reverse out the polynomial coefficients. It's similar to the Maclaurin Series replacing xk/k! by C(n,k). Once in this form the sequence is also easy to "integrate" (i.e. calculate partial sums) as this is only a shift of index. Here's the example for n3: n: 0 1 2 3 4 ... f(n): 0 1 8 27 64 ... D f(n): 1 7 19 37 ... D2 f(n): 6 12 18 ... D3 f(n): 6 6 ... f(n) = n3 = 6 C(n,3) + 6 C(n,2) + C(n,1) F(n) = n3 = 6 C(n,4) + 6 C(n,3) + C(n,2) F(n) = ((6(n-3)/4 + 6)(n-2)/3 + 1) (n-1)n/2 F(n) = n4/4 - n3/2 + n2/4

 Question about the matrix mappingMessage #11 Posted by Namir on 11 June 2011, 7:59 p.m.,in response to message #5 by Gerson W. Barbosa The matrices shown in theses threads seem to have two indexing schemes: 1. The sequence index where the index is also equal to the value of the element. The first element in the "spiral" matrix is 1, the second is 2, and so on. 2. the row/column index of the matrix as seen as a more traditional matrix. My question is this, given a "spiral" matrix with N rows and N columns, when is the relationship between the above two indexing schemes? So for N rows and N columns, the row/column indices (i,j) correspond to what spiral index/value?? Namir

 Re: Question about the matrix mappingMessage #12 Posted by Gerson W. Barbosa on 11 June 2011, 10:28 p.m.,in response to message #11 by Namir Namir, This has not to do with your question, but I think I should mention a minor omission: Instead of "= 2*Sum(n=1,n,n^2) - T(n-1) + (n -1)/2 where T(n-1) is the nth number," It should have read "= 2*Sum(n=1,n,n^2) - T(n-1) + (n -1)/2 where T(n-1) is the nth triangular number," I hope this hasn't caused any confusion. Best regards, Gerson.

 Re: Question about the matrix mappingMessage #13 Posted by Namir on 12 June 2011, 5:42 a.m.,in response to message #12 by Gerson W. Barbosa Gerson, As I slept last night, my unconscious mind went to work to answer my question. I present pseudo-code for two procedures that map between the serial index of the matrix elements and the row/column indices: Given dimension of matrix BigN and index IdxVal. Find row and column index of matrix element containing IdxVal If N is odd then M = (BigN+1) / 2 Else M = BigN / 2 End If row = M col = M Idx = 1 N=1 do # extend the spiral to the next level col = col + 1 Idx = Idx + 1 LastN = N N = N + 2 if Idx > BigN^2 then exit if Idx = IdxVal then return (row,col) # move downward for i = 1 to LastN row = row + 1 Idx = Idx + 1 if Idx = IdxVal then return (row,col) end # move to the left for j = 1 to N - 1 col = col - 1 Idx = Idx + 1 if Idx = IdxVal then return (row,col) end # move up for i = 1 to N - 1 row = row - 1 Idx = Idx + 1 if Idx = IdxVal then return (row,col) end # move to the right for j = 1 to N - 1 col = col + 1 Idx = Idx + 1 if Idx = IdxVal then return (row,col) end loop end procedure Given dimension of matrix BigN and row,col) indices. Find index IdVal of matrix element at (rowVal,colVal) If N is odd then M = (BigN+1) / 2 Else M = BigN / 2 End If row = M col = M Idx = 1 N=1 do # extend the spiral to the next level col = col + 1 Idx = Idx + 1 LastN = N N = N + 2 if Idx > BigN^2 then exit if row = rowVal And col = colVal then return Idx # move downward for i = 1 to LastN row = row + 1 Idx = Idx + 1 if row = rowVal And col = colVal then return Idx end # move to the left for j = 1 to N - 1 col = col - 1 Idx = Idx + 1 if row = rowVal And col = colVal then return Idx end # move up for i = 1 to N - 1 row = row - 1 Idx = Idx + 1 if row = rowVal And col = colVal then return Idx end # move to the right for j = 1 to N - 1 col = col + 1 Idx = Idx + 1 if row = rowVal And col = colVal then return Idx end loop end procedure The two pseudo-code procedures basically perform a brute-force sequential search starting with the first element of the sequence (located in the center of the matrix) and then searching clockwise in a spiral manner. If the matrix elements increment by values greater than one, then you need to track the index and the search value separately. The code would require some minor modification. Edited: 12 June 2011, 9:07 a.m.

 Re: Question about the matrix mappingMessage #14 Posted by Allen on 13 June 2011, 8:57 p.m.,in response to message #13 by Namir Namir, If you are interested in "navigating" Ulam's spiral, I strongly suggest this posting from Feb 2011 I spent dozens of hours finding a closed-form solution (and a 32-byte 42S program) to do exactly that.

 Re: A new 6-problem challenge (free42 or 42s)Message #15 Posted by Gerson W. Barbosa on 11 June 2011, 2:37 p.m.,in response to message #3 by Allen Allen, If the labels A through J are allowed and the stack is filled with n then a 19-byte solution is possible. This first execution could be a bit cumbersome. For instance, for n=5 and n=, assuming LBL A has been used: 5 ENTER ENTER ENTER XEQ ENTER SIGMA+ SIGMA+ ENTER --> 101 7 ENTER ENTER ENTER R/S --> 261 If the stack should not be previously filled and the label A is used, then the program size is 22 bytes and it is 16-step long, final END included. * Regards, Gerson. ---- * Never mind. Found the answer in you PDF file (I should have used a numeric label). BTW, there's a line numbering mistake in your third solution to #28. Edited: 13 June 2011, 12:10 a.m.

 Re: A new 6-problem challenge (free42 or 42s)Message #16 Posted by Allen on 10 June 2011, 11:22 p.m.,in response to message #1 by Allen I don't know how good this metric is: > 240 : Beginner 230-220 : Advanced 220-210 : Very Good! 210-200 : Black Belt!! < 200 : Grand Master I have reason to believe a Grand Master could get below 190 based on the grading and bonus above. Edited: 10 June 2011, 11:22 p.m.

 Re: A new 6-problem challenge (free42 or 42s)Message #17 Posted by Kiyoshi Akima on 11 June 2011, 1:04 p.m.,in response to message #16 by Allen Quote: I don't know how good this metric is: I quite agree. I used an HP 35S, but got the total step count down well below 65.

 Re: A new 6-problem challenge (free42 or 42s)Message #18 Posted by Thomas Klemm on 11 June 2011, 7:52 p.m.,in response to message #1 by Allen Problem 1 00 { 45-Byte PRGM } 00 { 39-Byte PRGM } 00 { 34-Byte PRGM } 00 { 39-Byte PRGM } 00 { 39-Byte PRGM } 00 { 37-Byte PRGM } 00 { 39-Byte PRGM } 01 LBL "E1.0" 01 LBL "E1.1" 01 LBL "E1.2" 01 LBL "E1.3" 01 LBL "E1.4" 01 LBL "E1.5" 01 LBL "E1.6" 02 1 02 STO OO 02 STO OO 02 STO OO 02 STO OO 02 STO OO 02 CLRG 03 - 03 CLS 03 CLST 03 CLS 03 CLS 03 CLS 03 GTO 01 04 STO 00 04 GTO 02 04 DSE 00 04 GTO 14 04 GTO 06 04 GTO 01 04 LBL 00 05 3 05 LBL 00 05 LBL 00 05 LBL 00 05 LBL 10 05 LBL 00 05 RCL ST X 06 XEQ 00 06 RCL 00 06 RCL 00 06 RCL 00 06 RCL 00 06 27030 06 15 07 5 07 3 07 3 07 15 07 15 07 RCL 00 07 MOD 08 XEQ 00 08 MOD 08 MOD 08 MOD 08 MOD 08 15 08 X<>Y 09 + 09 X=0? 09 RCL 00 09 SF 25 09 LASTX 09 MOD 09 STO+ IND ST Y 10 15 10 GTO 01 10 5 10 X#0? 10 2 10 BIT? 10 LBL 01 11 XEQ 00 11 RCL 00 11 MOD 11 GTO IND ST X 11 / 11 GTO 01 11 DSE ST X 12 - 12 5 12 * 12 RCL 00 12 - 12 RCL 00 12 GTO 00 13 RTN 13 MOD 13 X#0? 13 S+ 13 SF 25 13 S+ 13 RCL 00 14 LBL 00 14 X=0? 14 SIGN 14 LBL 01 14 GTO IND ST X 14 LBL 01 14 RCL 03 15 RCL 00 15 GTO 01 15 1 15 LBL 02 15 RCL 00 15 DSE 00 15 + 16 RCL/ ST Y 16 GTO 02 16 - 16 LBL 04 16 S+ 16 GTO 00 16 RCL 05 17 IP 17 LBL 01 17 RCL 00 17 LBL 07 17 LBL 00 17 SUM 17 + 18 1 18 RCL 00 18 * 18 LBL 08 18 LBL 03 18 END 18 RCL 06 19 + 19 S+ 19 - 19 LBL 11 19 LBL 05 19 + 20 2 20 LBL 02 20 DSE 00 20 LBL 13 20 LBL 06 20 RCL 09 21 COMB 21 DSE 00 21 GTO 00 21 LBL 14 21 DSE 00 21 + 22 * 22 GTO 00 22 END 22 DSE 00 22 GTO 10 22 RCL 10 23 END 23 SUM 23 GTO 00 23 SUM 23 + 24 END 24 SUM 24 END 24 RCL 12 25 END 25 + 26 END E1.0: uses COMB to calculate sum of natural numbers E1.1: uses brute force E1.2: no jumps involved E1.3: switch on i MOD 15 using error flag 25 E1.4: same as E1.3 but uses symmetry E1.5: 2703010 = 1101001100101102 E1.6: add i to register i MOD 15 and select partial sum at end of loop Solution: 233,168 Shortest: 27 Bytes Problem 2 00 { 55-Byte PRGM } 00 { 34-Byte PRGM } 01 LBL "E2.0" 01 LBL "E2.1" 02 5 02 1 03 SQRT 03 X<>Y 04 * 04 0 05 LASTX 05 ENTER 06 1 06 RDN 07 + 07 LBL 00 08 2 08 X>Y? 09 / 09 GTO 01 10 3 10 STO+ ST T 11 Y^X 11 RCL+ ST Z 12 STO 00 12 STO+ ST Z 13 LN 13 X<> ST Z 14 X<>Y 14 STO+ ST Z 15 LN 15 GTO 00 16 X<>Y 16 LBL 01 17 / 17 R^ 18 1.5 18 END 19 + 20 IP 21 RCL 00 22 X<>Y 23 Y^X 24 1 25 - 26 RCL 00 27 1 28 - 29 / 30 5 31 SQRT 32 / 33 0.5 34 + 35 IP 36 END E2.0: uses formula; not correct for small values E2.1: uses 3 iterations in one step: y = 3y + 2x; x = 2y + x Solution: 4,613,732 Shortest: 27 Bytes Problem 3 00 { 33-Byte PRGM } 01 LBL "E3" 02 STO 00 03 2 04 LBL 00 05 X^2 06 RCL 00 07 XY 25 GTO 02 25 STO 03 26 RCL 02 26 LBL 02 27 RCL 03 27 DSE 01 28 XY 29 DSE 00 30 STO 03 30 GTO 00 31 VIEW ST X 31 RCL 03 32 LBL 02 32 END 33 ISG 01 34 GTO 01 35 DSE 00 36 GTO 00 37 RCL 03 38 END E4.0: displays correct result fast E4.1: is very slow Solution: 906,609 Shortest: 54 Bytes Problem 5 00 { 31-Byte PRGM } 01 LBL "E5" 02 STO 00 03 GTO 02 04 LBL 00 05 RCL 00 06 ENTER 07 X<> ST Z 08 STO* ST Z 09 LBL 01 10 X<>Y 11 RCL ST Y 12 MOD 13 X#0? 14 GTO 01 15 RDN 16 / 17 LBL 02 18 DSE 00 19 GTO 00 20 END calculates lcm(1, 2, ..., 20) Solution: 232,792,560 Shortest: 26 Bytes Problem 6 00 { 27-Byte PRGM } 00 { 24-Byte PRGM } 01 LBL "E6.0" 01 LBL "E6.1" 02 ENTER 02 STO 00 03 ENTER 03 CLST 04 X^2 04 LBL 00 05 1 05 RCL 00 06 - 06 STO + ST Z 07 * 07 X^2 08 X<>Y 08 + 09 3 09 DSE 00 10 * 10 GTO 00 11 2 11 X<>Y 12 + 12 X^2 13 * 13 X<>Y 14 12 14 - 15 / 15 END 16 END E6.0: uses formula: (n-1)n(n+1)(3n+2)/12 E6.1: uses brute force Solution: 25,164,150 Shortest: 17 Bytes Problem 28 00 { 27-Byte PRGM } 01 LBL "E28" 02 ENTER 03 ENTER 04 ENTER 05 4 06 * 07 3 08 + 09 * 10 8 11 + 12 * 13 9 14 - 15 6 16 / 17 END uses formula: (4n3 + 3n2 + 8n - 9)/6 Solution: 669,171,001 Shortest: 21 Bytes Summary Problem Bytes 1 27 2 27 3 28 4 54 5 26 6 17 28 -4 Total 175 Thanks for the interesting challenge. My favorite was problem 1. It was fun trying to find yet another solution. Now I'm going to have a look at the other contributions. Kind regards Thomas

 Re: A new 6-problem challenge (free42 or 42s)Message #19 Posted by Gerson W. Barbosa on 11 June 2011, 10:00 p.m.,in response to message #18 by Thomas Klemm Excellent work as always, Thomas! Please allow me a small suggestion to save one step in your "E28": Replace 04 ENTER 05 4 06 * with 04 STO+ ST X 05 STO+ ST X Best regards, Gerson.

 Re: A new 6-problem challenge (free42 or 42s)Message #20 Posted by Thomas Klemm on 12 June 2011, 12:29 a.m.,in response to message #19 by Gerson W. Barbosa Thank you, for pointing that out. I forgot about rule 7. Thomas

 Re: A new 6-problem challenge (free42 or 42s)Message #21 Posted by Gerson W. Barbosa on 12 June 2011, 3:29 p.m.,in response to message #20 by Thomas Klemm Well, that's not exactly a rule that had to be followed. As I did only #28, I tried at least to make it as short as possible. How does your 21-byte version look like? 22 bytes was my best, by using LBL A in the first line. (*) Here is an interesting fact about this problem: when n is 1, 3, 11, 35 and 147 the sums are perfect squares. I would bet there are no others, but I may be wrong. Best regards, Gerson. 00 { 52-Byte Prgm } 01>LBL "PS" 02 1.99902 03 STO 00 04>LBL 00 05 RCL 00 06 IP 07 XEQ A 08 SQRT 09 FP 10 X=0? 11 PSE 12 ISG 00 13 GTO 00 14 RTN 15 LBL A 16 ENTER 17 ENTER 18 STO+ ST X 19 STO+ ST X 20 3 21 + 22 * 23 8 24 + 25 * 26 9 27 - 28 6 29 / 30.END. ---- (*) Never mind. Found the answer in Allen's PDF file. Edited: 13 June 2011, 12:14 a.m.

 Re: A new 6-problem challenge (free42 or 42s)Message #22 Posted by Allen on 12 June 2011, 1:27 a.m.,in response to message #18 by Thomas Klemm Thomas, very nice! I'm still studying some of your solutions! I'll post my own solutions later today .... Here's a quick table: 42S results Prob. Bytes Steps O(?) Desc ============================================================= 1 39 22 1 sum 3,5 multiples 2 27 19 ~LN(N) sum even F(n) nums 3 34 23 ? factor odd 12-digit 4 60 35 N^2 abccba palindrome 5 24 18 ~N LOG(N) LCM (1..20) 6 14 12 N sum sq. - sq. sum 28 19 14 N sum ulam corners Bonus -25 0 n/a n/a ============================================================= 192 129 (143 w/ bonus) Note:All my byte/step counts assume 1 byte local label at the beginning. We have basically the same size/solution/algorithm for Problem 2 Your method is MUCH smaller (>5 bytes difference) for 1,3,4 and mine is SLIGHTLY smaller (<5 bytes difference) for 5 and 6, 28. Fantastic work!! My looping solution for BONUS problem: Input: 500 R/S 00 { 19-Byte Prgm } 01>LBL 01 02 STO 01 leave counter on stack and initialize 01 for DSE 03>LBL 02 04 RCL 01 05 ENTER Save a copy for step 08 06 STO+ ST X double it 07 X^2 = 4N^2 08 + = 4N^2+N 09 + accumulate prev. sums together in X register 10 DSE 01 Main loop back for counter 11 GTO 02 12 4 13 × X: 4 (sum(4N^2+N)+N) 14 ISG ST X X: 4 (sum(4N^2+N)+N)+1 15 .END. Uses the same eq as the horner solution, but rewritten to save space: Edited: 12 June 2011, 1:54 a.m.

 Re: A new 6-problem challenge (free42 or 42s)Message #23 Posted by Allen on 12 June 2011, 5:56 p.m.,in response to message #18 by Thomas Klemm Note: available with RAW files for free42 in PDF File download. Problem 1 =============================================== 00 { 39-Byte Prgm } 01>LBL 00 02 3 03 XEQ 01 04 5 05 XEQ 01 06 + 07 15 08 XEQ 01 09 - 10 2 11 ÷ 12 RTN 13>LBL 01 14 999 15 RCL ST Y 16 BASE÷ 17 ENTER 18 ISG ST X 19 × 20 × 21 × 22 RTN 23 .END. Problem 2 ============================================== 00 { 27-Byte Prgm } 01>LBL 00 02 STO 01 03 SIGN Places 1 on stack 04 ENTER 05 STO+ ST X 2 on stack 06 STO 02 initializes sum with 2 07>LBL 01 Main loop 08 STO+ ST Y \ 09 RCL+ ST Y | Fibonacci sequence for even values 10 STO+ ST Y |(every third term) 11 X<>Y / 12 RCL 01 13 XLBL 02 <- End of looping program 19 RCL 02 Recall 20 .END. Problem 3 ========================================================= Note: Uses Fermat's method and can be pretty fast or slow dep. on input. 00 { 34-Byte Prgm } 01>LBL 00 02 STO 06 03 STO 01 04 SQRT 05 IP Should be Ceil(sqrt(n)) but step 08 adds 1 06 ENTER for ROLLDN in step 7 to cleanup test in st.16 07>LBL 01 <-- Main Loop 08 Rv 09 ISG ST X add 1 to X register 10 ENTER NOP 11 ENTER duplicate X for next loop 12 X^2 13 RCL- 01 14 SQRT 15 FP 16 X!=0? Check N-a^2 to see if it’s of form b^2 17 GTO 01 If not, loop and add one to stack 18 RCL ST L 19 RCL+ ST Z convert to a+b 20 STOP 21 RCL÷ 06 22 1/X 23 XEQ 00 24 .END. Problem 4 ============================================== Note: Fairly slow since it tests the whole space. Leverages ATOX-ATOX PALINDROME code snippet from Hpmuseum. 00 { 60-Byte Prgm } 01>LBL 01 02 999 Initial counter at 999 03 STO 00 04 STO 01 05>LBL 02 Loop 1: decrementing by 11 from 990 06 990 (faster but more expensive: use 990.11011 for STO 02 07 STO 02 08>LBL 03 Loop 2: Calculating a new product 09 RCL 02 recall the Loop 1 counter and 10 RCL× 01 A*B (where B is a multiple of 11) 11 CLA Clear alpha reg 12 AIP Load X into Alpha REG and use to check ends 13>LBL 04 Loop 3: Checking Alpha Reg for Palindromes 14 ALENG If null alpha reg, 15 X=0? The product must be a palindrome 167 GTO 05 Go to test function for Max(Palindrome) 17 -1 18 AROT Destructively compares first and last character 19 ATOX in alpha reg 20 ATOX 21 X=Y? If outer set matches 22 GTO 04 Checks next set in 23 DSE 02 With branching function for Loop 2 24 GTO 03 “10 STO– 02“ here to hasten search only by 11’s 25 DSE 01 Decrement counter--add 26 GTO 02 Return to loop 1 27>LBL 05 Max(Palindrome) Subroutine 28 RCL 00 Pull Last Palindrome (999 on first loop) 29 RCL 02 30 RCL× 01 31 X>Y? Compare product with old value 32 STO 00 keep if greater 33 DSE 01 34 GTO 02 Return to Loop 1 until 999 is depleted (saves space) 35 RCL 00 Recall max(Palindrome) 36 .END. Problem 5 ================================================= Note:Very compact version of euclid's recurrence and LCM formula. ( See PDF for more info) 00 { 24-byte Prgm } 01>LBL 00 02 STO 00 <- Cumulative LCM (starts with input value) 03 STO 01 <- Decrement Counter 04>LBL 01 Counter loop 05 RCL 01 06 STO× 00 Store first part of LCM=abs(a*b) 07>LBL 02 Begin Euclid Recurrence to find GCD(A,B) 08 X<>Y (largest number on bottom) 09 RCL ST Y OVER command in RPL. AB Stack is now A B A 10 MOD 11 X>0? 12 GTO 02 take largest and div. again if greater than 0 13 XY MAX(0,R) R is the LCM of STEP 05 and STEP 06 15 STO÷ 00 second part of LCM formula = product\ GCD(A,B) 16 RCL 00 Recall Cumulative LCM register- COMPLETE! 17 DSE 01 check Register 01 and 18 GTO 01 Return to Counter loop if not finished 19 .END. Problem 6 ==================================================== Note: Leverages Summation registers 11 SUM(X) and 12 SUM(X^2) 00 { 14-Byte Prgm } 01>LBL 01 02 STO 01 <- decrement counter for initial value 03 CL\Sigma clear stat regs 04>LBL 02 <- Main loop 05 RCL 01 recall the counter 06 \Sigma+ adds 1 to count, MEM11+=N and MEM12+=N^2 07 DSE 01 check counter 08 GTO 02 and loop 09 RCL 11 otherwise recall SUM(N) 10 X^2 SUM(N)^2 11 RCL- 12 12 - SUM(N)^2 – SUM(N^2) 13 .END.

Go back to the main exhibit hall