Batrachions

# 3 Batrachions for the HP-41

Overview

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

-These programs compute the successive terms of 3 recursive sequences

-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