hp41programs

Batrachions

3 Batrachions for the HP-41


Overview
 

  1°)  Hofstadter's Batrachion
  2°)  Conway's Batrachion
  3°)  Mallows's Batrachion
 

-These programs compute the successive terms of 3 recursive sequences
 

1°) Hofstadter's Batrachion
 

-The sequence is defined by     H(1) = H(2) = 1  ;   H(n) = H(n-H(n-1)) + H(n-H(n-2))
 

Data Registers:     R00 = 0  ;  R01 = H(1)  ;  R02 = H(2)  ; .......... ;  Rnn = H(n)
Flags: /
Subroutines: /
 
 

01  LBL "HOF"
02  .1
03  %
04  1
05  STO 01		 06  ST+ Y
07  0
08  STO 00      
09  STO 02
10  LBL 01		 11  RCL Z
12  X<>Y
13  -
14  RDN
15  RCL IND T		 16  X<>Y
17  ST- T
18  X<> L
19  X<>Y
20  RCL IND T		 21  +
22  STO IND Z
23  ISG Z
24  GTO 01
25  END

 
    ( 43 bytes / SIZE nnn+1 )
 
 

      STACK        INPUTS      OUTPUTS
           Z             /        1+n.nnn
           Y             /         H(n-1)
           X             n          H(n)

 
Example:     100  XEQ "HOF"  >>>>  H(100) = 56  ( in 39 seconds )            and  H(n) is in register Rnn  for  n < 101

-The firs few terms are:
 

    n     1     2     3     4     5     6     7     8     9    10
 H(n)     1     1     2     3     3     4     5     5     6     6

 

2°) Conway's Batrachion
 

-The sequence is defined by     C(1) = C(2) = 1  ;   C(n) = C(C(n-1)) + C(n-C(n-1))        ( n > 2 )
 

Data Registers:     R00  unused  ;  R01 = C(1)  ;  R02 = C(2)  ; .......... ;  Rnn = C(n)
Flags: /
Subroutines: /
 
 

01  LBL "CNW"
02  3
03  X<=Y?
04  GTO 00
05  SIGN
06  RTN		 07  LBL 00       
08  X<>Y
09   E3
10  /
11  +
12  1		 13  STO 01
14  STO 02       
15  LBL 01
16  RCL Y
17  X<>Y
18  -		 19  X<>Y
20  RCL IND Y
21  RCL IND L
22  +
23  STO IND Y
24  ISG Y		 25  GTO 01       
26  END
 

 
    ( 42 bytes / SIZE nnn+1 )
 
 

      STACK        INPUTS      OUTPUTS
           Y             /        1+n.nnn*
           X             n          C(n)

   * if n > 2

Example:    100  XEQ "CNW"  >>>>   C(100) = 57  ( in 30 seconds )            and  C(n) is in register Rnn  for  n < 101

-The first few terms are
 

    n     1     2     3     4     5     6     7     8     9    10
 C(n)     1     1     2     2     3     4     4     4     5     6

-We have   C(2k) = 2k-1
-The graph of the ratio  C(n)/n  looks like a hopping frog and  C(n)/n tends to 1/2 as n tends to infinity.

C(n)/n
   |       *
   |     *  *          *
   |   *     *      *    *              *
   |  *       *   *        *       *       *
   | *         **            *  *             *
--|*-------*----------*------------*------------------------- n
 

3°) Mallows's Batrachion
 

-The sequence is defined by     M(1) = M(2) = 1  ;   M(n) = M(M(n-2)) + M(n-M(n-2))
 

Data Registers:     R00 = 0  ;  R01 = M(1)  ;  R02 = M(2)  ; .......... ;  Rnn = M(n)
Flags: /
Subroutines: /
 
 

01  LBL "MLW"
02  .1
03  %
04  1
05  STO 01		 06  STO 02       
07  ST+ Y
08  0
09  STO 00
10  LBL 01		 11  X<>Y
12  RCL Z       
13  X<>Y
14  -
15  RDN		 16  RCL IND T
17  RCL IND L
18  +
19  STO IND Z
20  ISG Z		 21  GTO 01       
22  END

 
    ( 38 bytes / SIZE nnn+1 )
 
 

      STACK        INPUTS      OUTPUTS
           Z             /        1+n.nnn
           Y             /         M(n-1)
           X             n          M(n)

 
Example:     260  XEQ "MLW"  >>>>  M(260) = 180  ( in 85 seconds )            and  M(n) is in register Rnn  for  n < 261

-The first few terms are
 

    n     1     2     3     4     5     6     7     8     9    10
 M(n)     1     1     2     3     3     4     5     6     6     7

 

Reference:

[1] Clifford A. Pickover - "Keys to Infinity" - John Wiley & Sons -  ISBN  0-471-11857-5