mini-challenge « Next Oldest | Next Newest »

 ▼ Don Shepherd Posting Freak Posts: 1,392 Threads: 142 Joined: Jun 2007 02-24-2008, 11:47 AM 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. ▼ Mad Dog ebaycalcnut Member Posts: 124 Threads: 17 Joined: Dec 2006 02-24-2008, 12:32 PM Kind of Bible Code-ish.... However, the Bible Code folks do equidistant spacing to find predictions. Allen Senior Member Posts: 562 Threads: 27 Joined: Oct 2006 02-24-2008, 12:47 PM This looks surprisingly like a map of Paris' arrondissements . Perhaps Mike D. can help here. :) Gerson W. Barbosa Posting Freak Posts: 2,761 Threads: 100 Joined: Jul 2005 02-24-2008, 04:47 PM 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 ``` Allen Senior Member Posts: 562 Threads: 27 Joined: Oct 2006 02-24-2008, 05:51 PM 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. ▼ Don Shepherd Posting Freak Posts: 1,392 Threads: 142 Joined: Jun 2007 02-24-2008, 08:16 PM 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. ▼ Allen Senior Member Posts: 562 Threads: 27 Joined: Oct 2006 02-25-2008, 12:15 AM 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. ▼ Don Shepherd Posting Freak Posts: 1,392 Threads: 142 Joined: Jun 2007 02-25-2008, 09:13 AM 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 ▼ Allen Senior Member Posts: 562 Threads: 27 Joined: Oct 2006 02-25-2008, 09:17 PM 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. ▼ Allen Senior Member Posts: 562 Threads: 27 Joined: Oct 2006 02-25-2008, 09:49 PM ``` 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.

 Possibly Related Threads... Thread Author Replies Views Last Post HPCC Mini Conference 2013 hugh steers 6 1,473 09-13-2013, 04:27 PM Last Post: BruceH Picture from the Mini-HHC (LA) Geir Isene 11 2,084 07-07-2013, 01:06 PM Last Post: Jim Horn My birthday, so a little commemorative mini-challenge ! Valentin Albillo 43 5,561 03-07-2013, 03:44 AM Last Post: Walter B WP 34S mini-challenge (B) Gerson W. Barbosa 17 3,088 12-27-2012, 04:39 PM Last Post: Marcus von Cube, Germany Mini-challenge: HHC2012 RPL programming contest with larger input David Hayden 14 2,413 10-05-2012, 10:36 PM Last Post: David Hayden HP41 / SY41CL Mini-B USB Power Connector (Module) Matt Kernal 5 2,437 07-08-2012, 06:23 PM Last Post: Diego Diaz HP-15C (& LE!) 11-11-11 Mini-Challenge Valentin Albillo 28 4,578 11-14-2011, 08:12 AM Last Post: Valentin Albillo Mini challenge. CEIL / FLOOR in RPN M. Joury 47 7,557 10-31-2011, 10:11 AM Last Post: M. Joury A simple wp34s mini-challenge Gerson W. Barbosa 29 4,738 06-29-2011, 06:02 PM Last Post: Guenter Schink HP-15C mini-challenge (Project Euler - problem #1) Gerson W. Barbosa 14 2,701 05-08-2011, 11:08 AM Last Post: Marcus von Cube, Germany

Forum Jump: