The Museum of HP Calculators

HP Forum Archive 20

[ Return to Index | Top of Index ]

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 method
Message #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 method
Message #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 method
Message #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

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

Using the Horner-like schema the expression can be rewritten to:

Plug that expression into WolframAlpha to get:

This is in accordance with what you find at the on-line encyclopedia of integer sequences.

Cheers
Thomas


Explanation:

D C(n,k) = C(n+1,k) - C(n,k) = C(n,k-1)

Di C(n,k) = C(n,k-i)

C(n,0) = 1 for all n => C(0,0) = 1

C(0,k) = 0 for all k > 0

Edited: 14 June 2011, 1:20 a.m. after one or more responses were posted

                                                
Re: Bonus problem and horner method
Message #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 method
Message #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 mapping
Message #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 mapping
Message #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 mapping
Message #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 mapping
Message #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 X<Y?
08 GTO 02
09 LASTX
10 MOD
11 X=0?
12 GTO 01
13 LASTX
14 1
15 +
16 GTO 00
17 LBL 01
18 LASTX
19 STO/ 00
20 GTO 00
21 LBL 02
22 END

  • uses brute force

Solution: 6,857
Shortest: 28 Bytes


Problem 4

00 { 75-Byte PRGM }           00 { 61-Byte PRGM }  
01 LBL "E4.0"                 01 LBL "E4.1"        
02 CLRG                       02 CLRG              
03 999.1                      03 999               
04 STO 00                     04 STO 00            
05 LBL 00                     05 LBL 00            
06 RCL 00                     06 RCL 00            
07 IP                         07 STO 01            
08 0.999                      08 LBL 01            
09 +                          09 RCL 00            
10 STO 01                     10 RCL 01            
11 LBL 01                     11 *                 
12 RCL 00                     12 STO 02            
13 IP                         13 100001            
14 RCL 01                     14 MOD               
15 IP                         15 10010             
16 *                          16 MOD               
17 STO 02                     17 1100              
18 100001                     18 MOD               
19 MOD                        19 X#0?              
20 10010                      20 GTO 02            
21 MOD                        21 RCL 02            
22 1100                       22 RCL 03            
23 MOD                        23 X<Y?              
24 X#0?                       24 X<>Y              
25 GTO 02                     25 STO 03            
26 RCL 02                     26 LBL 02            
27 RCL 03                     27 DSE 01            
28 X<Y?                       28 GTO 01            
29 X<>Y                       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 X<Y? if input value exceeded, skip to end 14 GTO 02 15 Rv otherwise remove input value and 16 STO+ 02 accumulate next even 17 GTO 01 Return to main loop 18>LBL 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 X<Y? 14 X<>Y 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.


[ Return to Index | Top of Index ]

Go back to the main exhibit hall