Searching for the Most Wondrous Number

Due by class time Tuesday, March 7

Instructions: Please write out your program definitions on paper and bring them with you to class on Tuesday. We will go over the solutions together in class. If you wish, you may work with another student on this assignment.

1. The FlooP code for the WONDROUS? program is given below, along with the "Scheme-ified" version of the code that can be copy-and-pasted directly into the FlooP interpreter. Change the name of this program to COUNT-STEPS and modify it so that instead of outputting YES or NO, it outputs the number of steps that N takes to reach 1, without printing anything out. For example, calling your COUNT-STEPS program with 10 should output 6, since 10 takes 6 steps to reach 1, while calling COUNT-STEPS with 27 should output 111, since 27 takes 111 steps to reach 1, as shown below:

   ==> (count-steps 10)
   6
   ==> (count-steps 27)
   111
       
   
   DEFINE PROCEDURE ''WONDROUS?'' [N]:
   BLOCK 0: BEGIN
             IF N = 0, THEN:
             QUIT BLOCK 0;
             CELL(0) <= 0;
             MU-LOOP:
             BLOCK 1: BEGIN
                       PRINT N;
                       IF N = 1, THEN:
                       BLOCK 2: BEGIN
                                 OUTPUT <= YES;
                                 PRINT ''TOOK'', CELL(0), ''STEPS'';
                                 QUIT BLOCK 0;
                       BLOCK 2: END;
                       CELL(0) <= CELL(0) + 1;
                       IF REMAINDER [N, 2] = 0, THEN:
                       BLOCK 3: BEGIN
                                 N <= QUOTIENT [N, 2];
                                 QUIT BLOCK 1;
                       BLOCK 3: END;
                       N <= 3 × N + 1;
             BLOCK 1: END;
   BLOCK 0: END.
     
   (define procedure "wondrous?" (n)
     (block 0 begin
            (if (n = 0) then
                (quit block 0))
   	 ((cell 0) <= 0)
            (mu-loop
             (block 1 begin
                    (print n)
                    (if (n = 1) then
                        (block 2 begin
                               (output <= yes)
   			    (print "took" (cell 0) "steps")
                               (quit block 0)))
   		 ((cell 0) <= ((cell 0) + 1))
                    (if ((remainder n 2) = 0) then
                        (block 3 begin
                               (n <= (quotient n 2))
                               (quit block 1)))
                    (n <= ((3 * n) + 1))))))
   

2. Write a new BlooP program called MOST-WONDROUS-UP-TO that takes a number LIMIT as input and searches for the number N from 1 up to the specified LIMIT that requires the largest number of steps to reach 1, and reports the results. We could call this the "most wondrous" number up to LIMIT. Your program should use COUNT-STEPS as a helper function. Some examples are shown below:

   ==> (most-wondrous-up-to 10)
   MOST WONDROUS NUMBER FOUND IS 9 
   WHICH TOOK 19 STEPS 
   9
   ==> (most-wondrous-up-to 30)
   MOST WONDROUS NUMBER FOUND IS 27 
   WHICH TOOK 111 STEPS 
   27
   ==> (most-wondrous-up-to 100)
   MOST WONDROUS NUMBER FOUND IS 97 
   WHICH TOOK 118 STEPS 
   97
   

   What is the most wondrous number up to 1000, and how many steps does it take to reach 1? What about up to 10,000? Hint: Your program will need to make use of some additional variables to keep track of information as the search progresses. For example, you could use CELL(0) to store the current value of N being tested; CELL(1) to store the step-count of N (that is, how many steps N took to reach 1); CELL(2) to store the best (most wondrous) number found so far; and CELL(3) to store the step-count of the best number found so far.

   DEFINE PROCEDURE ''MOST-WONDROUS-UP-TO'' [LIMIT]:
   BLOCK 0: BEGIN
      ...
   BLOCK 0: END.