# HP Forums

Full Version: mini-challenge
You're currently viewing a stripped down version of our content. View the full version with proper formatting.

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.

Kind of Bible Code-ish.... However, the Bible Code folks do equidistant spacing to find predictions.

This looks surprisingly like a map of Paris' arrondissements . Perhaps Mike D. can help here. :)

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
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
```

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: 24 Feb 2008, 6:17 p.m.

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.

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.

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

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.

```
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.