mini-challenge - Printable Version +- HP Forums (https://archived.hpcalc.org/museumforum) +-- Forum: HP Museum Forums (https://archived.hpcalc.org/museumforum/forum-1.html) +--- Forum: Old HP Forum Archives (https://archived.hpcalc.org/museumforum/forum-2.html) +--- Thread: mini-challenge (/thread-133329.html) mini-challenge - Don Shepherd - 02-24-2008 OK, here is a challenge. Devise an RPN program or Solver solution to the following problem. Refer to this. Assume this pattern continues forever. I want to input a number, like 19, and the program must tell me the 4 adjacent numbers, like 6, 18, 40, and 20. I see the patterns of square numbers, but I'm not sure this will help me figure out the four numbers I am interested in. Re: mini-challenge - Mad Dog ebaycalcnut - 02-24-2008 Kind of Bible Code-ish.... However, the Bible Code folks do equidistant spacing to find predictions. Re: mini-challenge - Allen - 02-24-2008 This looks surprisingly like a map of Paris' arrondissements . Perhaps Mike D. can help here. :) Re: mini-challenge - Gerson W. Barbosa - 02-24-2008 That's Ulam Spiral. The following QBASIC program will generate a similar spiral. It is a slight adaptation of a BASIC program I found in an old book about an early Brazilian dot-matrix printer, by Victor Mirshawka (Grafix MTA: A Impressora ao Alcance de Todos). Apparently the author was not aware of Ulam Spiral, as he doesn't mention it in his printer application. Gerson. ```--------------- 10 OPTION BASE 0 30 INPUT N: CLS 32 PRINT "--------------------------------" 34 PRINT 40 DIM M(N + 1, N + 1) 50 Y = INT(N / 2 + .51) 60 X = Y 70 C = 1: D = 0 80 FOR K = 1 TO N 90 IF INT(K / 2) = K / 2 THEN 110 100 RESTORE 110 FOR A = 1 TO 2 120 E = D 130 READ D 140 FOR L = 1 TO K 150 M(Y, X) = C 160 IF C = N ^ 2 THEN 220 170 C = C + 1: Y = Y + D: X = X + E 180 NEXT L 190 NEXT A 200 NEXT K 220 FOR I = 1 TO N 230 FOR J = 1 TO N 240 PRINT TAB(J * 5); M(I, J); 250 NEXT J 260 PRINT : PRINT 270 NEXT I 280 DATA 1,0,-1,0 290 END ----------- ? 7 -------------------------------- 43 42 41 40 39 38 37 44 21 20 19 18 17 36 45 22 7 6 5 16 35 46 23 8 1 4 15 34 47 24 9 2 3 14 33 48 25 10 11 12 13 32 49 26 27 28 29 30 31 ``` spoiler 48g solution Re: mini-challenge - Allen - 02-24-2008 Don, Thanks for an interesting challenge. I think this may be smaller on the 42S, but I had a 48GX on the desk, so here is an unoptimized 48g solution. I use a 'corner and sides' approach whereby the FLOOR and CEIL of the Square roots are used to generate the corners and then determine from the max corner which side the input resides on. NOTE: Assumes 1 and 2 are trivial cases not to be calculated. e.g. if input=1 then {2 4 6 8} and likewise for 2. The program (not optimized for either size or speed): ```Bytes: 255 Checksum:#64353d Variables used: 1 Local, 0 Global Flags used: 01 << 1 CF -> N ; set up FLAG1 as odd/even increment for Floor/Ceil loop << 2 2 ; This skips 1 and 2 as input ( see assumptions) DO DUP SQRT 1 ; Main loop to determine the corners ( 7,10,13,17,21...) IF FS? ; Test for first or second corner between THEN CIEL 1 CF ; perfect squares. ELSE FLOOR 1 SF ; Corner numbers are alternate END ; cv2=cv1+floor(sqrt(cv1)) OR + ; cv2=cv1+ ceil(sqrt(cv1)) SWAP 1 + SWAP ; increment corner counter UNTIL DUP N >= ; Stop if you are at the corner or side END ; gives side number(s) and corner value IF DUP N == ; if the input IS the corner number THEN SWAP 2 * 3 + ; use corner formula DUP 2 + ->LIST ; {2*s+3 2*s+5} ELSE SWAP 4 - ; else use side formula: {-2 2} * {-3 11} ADD ; {-3-2*(s-4) 11+2*(s-4)} END {-1 1} + ; All solutions have N+1 and N-1 DUP DUP / N * ADD ; Adding N to all list values {-1 1 s1 s2) SWAP DROP SORT ; Clean stack and sort >> >> ``` Example (sorted) results: ```4 {1 3 5 15} 5 {4 6 16 18} 9 {2 8 10 24} 35 {16 34 36 62} 36 {17 35 37 63} 151 {106 150 152 204} ``` edited to add comments Edited: 24 Feb 2008, 6:17 p.m. Re: spoiler 48g solution Re: mini-challenge - Don Shepherd - 02-24-2008 Thanks Gerson and Hudendai. Yes, Gerson, I had read about that pattern of prime numbers going along the diagonals on an arrangement like this, and that is fascinating. I didn't realize that its name was the Ulam Spiral, however. Hudendai, thanks for your 48 solution, I am impressed! I'm going to translate it to RPN and maybe try it on my HP65. Re: 76 byte 42S solution Re: mini-challenge - Allen - 02-25-2008 Don, Since two of the answers are trivial, here is a 42s program to get the two hard ones. Works for all values of I except for 1. Commented RPN 'sides and corners' solution: ```bytes: 76 Flags: 01- Used for corners of form x^2+1 Registers: 00- I nput number 01- C orner counter value 02- N ext corner value 07- L ow solution difference 07- H igh solution difference 00 { 76-Byte Prgm } 01>LBL 00 ; program label, Program init. 02 CF 01 ; use flag 01 again for alternating loop 03 STO 00 ; 04 2 05 STO 01 06 STO 02 ; initial conditions C=2 and N=2 07>LBL 01 ; Loop to find the next highest corner value 08 1 ; and corner count 09 STO+ 01 ; increment corner value in loop 10 RCL 02 11 SQRT 12 IP 13 STO+ 02 ; add floor(sqrt(N)) to N 14 CLX ; place 0 on stack w/o push 15 FS? 01 16 1 17 STO+ 02 ; make ceil(sqrt(N)) if near x^2 18 FC?C 01 19 SF 01 ; Toggle Flag 01 20 RCL 02 21 RCL 00 22 X>Y? ; Test for the side, 23 GTO 01 ; repeat addition if too low 24 X=Y? ; Test for the corner 25 GTO 02 ; If yes, use corner algorithm 26 RCL 01 ; Otherwise use side algorithm 27 4 28 - 29 2 30 * 31 3 32 + 33 +/- 34 STO 07 ; L= -3-2*(C-4) 35 +/- 36 8 37 + 38 STO 08 ; (new) H=-L+8 39 GTO 03 ; Report results 40>LBL 02 ; Corner algorithm 41 RCL 01 42 2 43 * 44 3 45 + 46 STO 07 ;L=3+2*c 47 2 48 + 49 STO 08 ;H=L+2 50>LBL 03 ;Report results 51 RCL 07 52 RCL 00 53 + ;Y=I+L 54 RCL 08 55 RCL 00 56 + ;X=I+H 57 .END. ``` (edited) Example results: ```4 XEQ 00 Y: 1 X: 15 5 XEQ 00 Y: 16 X: 18 9 XEQ 00 Y: 2 X: 24 35 XEQ 00 Y: 16 X: 62 36 XEQ 00 Y: 17 X: 63 151 XEQ 00 Y: 106 X: 204 ``` Edited: 25 Feb 2008, 1:41 a.m. Re: 76 byte 42S solution Re: mini-challenge - Don Shepherd - 02-25-2008 Hudendai, that's great! I see what you mean about the 2 trivial solutions, which will always be one greater and one less than your input number. I'm going to enter this on my 65 and try it. Then I'm going to study it to see exactly how you did it! Thanks, Don Re: 76 byte 42S solution Re: mini-challenge - Allen - 02-25-2008 Don, I combined terms and was able to revise all solutions to this form ```First root : I+2c+3 (solution for both sides and corners) Second root: I-2c+5 (side only) I+2c+5 (corner only) I= input value c=side value (calculated) ``` As a result, I was able to re-write the 42s solution down to MUCH smaller size. 54 byte solution optomized for size:42S - Allen - 02-25-2008 ``` Note: 1/4th smaller than prev.version 1. uses updated corner/side selection algorithm noted above 2. uses ISG instead of counter 1 STO+ZZ 3. Uses Stat registers (11 and 13) to accumulate two values at one time instead of individual Registers 4. NO FLAGS USED 00 { 54-Byte Prgm } 01>LBL 00 02 STO 00 03 2 04 STO 01 05 STO 02 06>LBL 01 07 ISG 01 08 CLX 09 RCL 02 10 SQRT 11 IP 12 STO+ 02 13 RCL 02 14 SQRT 15 FP 16 X=0? 17 ISG 02 18 CLX 19 CL\Sigma 20 RCL 01 21 4 22 * 23 STO 04 24 2 25 / 26 RCL 00 27 + 28 ENTER 29 \Sigma+ 30 3 31 5 32 \Sigma+ 33 RCL 02 34 RCL 00 35 X>Y? 36 GTO 01 37 X=Y? 38 GTO 03 39 RCL 04 40 STO- 11 41>LBL 03 42 RCL 11 43 RCL 13 44 .END. ``` Edited: 26 Feb 2008, 8:45 a.m.