A new 6-problem challenge (free42 or 42s)
#1

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.

#2

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.

#3

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.

#4

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.

#5

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.

#6

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.

#7

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:

#8

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.

#9

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.

#10

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.

#11

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

#12

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

#13

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.

#14

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.

#15

Thank you, for pointing that out. I forgot about rule 7.

Thomas

#16

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.

#17

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.

#18

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.

#19

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.

#20

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

#21

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.

#22

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.

#23

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



Possibly Related Threads…
Thread Author Replies Views Last Post
  The latest version of Free42 is now a OS X Universal application..... zeno333 1 1,048 10-21-2012, 11:12 PM
Last Post: Matt Agajanian
  I need the last OS X "Universal" version of Free42..... zeno333 0 921 10-13-2012, 04:45 PM
Last Post: zeno333
  [OT] Free42 on the BlackBerry PlayBook Les Wright 1 1,094 02-25-2012, 10:56 AM
Last Post: Thomas Okken
  Free42 ? fhub 24 5,976 10-24-2011, 10:06 AM
Last Post: Egan Ford
  Re: Free42 - A Complex glitch? fhub 3 1,504 09-22-2011, 09:36 PM
Last Post: Thomas Okken
  42s questions and 42s vs 35s snaggs 13 5,506 09-19-2011, 02:44 AM
Last Post: snaggs
  Re: Free42 - A Complex glitch? Thomas Okken 23 5,379 09-18-2011, 09:10 PM
Last Post: Thomas Okken
  Free42 - A Complex glitch? Ángel Martin 23 5,699 09-14-2011, 09:39 AM
Last Post: Ángel Martin
  Thomas Okken and free42 ? sylvandb 5 1,767 07-11-2011, 09:18 PM
Last Post: sylvandb
  HP-15C mini-challenge (Project Euler - problem #1) Gerson W. Barbosa 14 3,971 05-08-2011, 11:08 AM
Last Post: Marcus von Cube, Germany

Forum Jump: