The Museum of HP Calculators

HP Forum Archive 18

[ Return to Index | Top of Index ]

mini-challenge
Message #1 Posted by Don Shepherd on 24 Feb 2008, 11:47 a.m.

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
Message #2 Posted by Mad Dog ebaycalcnut on 24 Feb 2008, 12:32 p.m.,
in response to message #1 by Don Shepherd

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

      
Re: mini-challenge
Message #3 Posted by Allen on 24 Feb 2008, 12:47 p.m.,
in response to message #1 by Don Shepherd

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

      
Re: mini-challenge
Message #4 Posted by Gerson W. Barbosa on 24 Feb 2008, 4:47 p.m.,
in response to message #1 by Don Shepherd

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
Message #5 Posted by Allen on 24 Feb 2008, 5:51 p.m.,
in response to message #1 by Don Shepherd

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
Message #6 Posted by Don Shepherd on 24 Feb 2008, 8:16 p.m.,
in response to message #5 by Allen

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
Message #7 Posted by Allen on 25 Feb 2008, 12:15 a.m.,
in response to message #6 by Don Shepherd

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
Message #8 Posted by Don Shepherd on 25 Feb 2008, 9:13 a.m.,
in response to message #7 by Allen

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
Message #9 Posted by Allen on 25 Feb 2008, 9:17 p.m.,
in response to message #8 by Don Shepherd

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
Message #10 Posted by Allen on 25 Feb 2008, 9:49 p.m.,
in response to message #9 by Allen


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.

[ Return to Index | Top of Index ]

Go back to the main exhibit hall