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(2^k) = 2^k-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