Question

A mathematical conjecture states that if we start with any positive number we can get to the value 1 by repeating 2 possible steps depending on the value of the current number. If the current value is even we divide the number by 2 and reapply the steps again (number / 2). If the number is odd we multiply the current number by 3 and add 1 to it and reply the previous steps again (number * 3 + 1). If we keep repeating the two possible alternative steps we will eventually get to the value 1 at which point we are done. Write a recursive function to test the conjecture. The function should return the number of times we had to recur through the function and the highest number that we generated by the use of the two possible steps during the process. Your solution will need to handle large numbers for processing. Sample run capture from the function Starting with 9 it took 19 steps; the highest number achieved 52. Starting with 27 it took 111 steps; the highest number achieved 9232. Starting with 837791 it took 162 steps; the highest number achieved 122288020. Starting with 837799 it took 524 steps; the highest number achieved 2974984576. Submit your commented solution as a text file along with the captured output from running the following set of values through your function. Format the output as in the sample captured runs above. Test Numbers 19 837,799 75,128,138,247 942,488,749,153,153

Answer 1

//C++ program

#include<iostream>
using namespace std;

long conjecture(long n,long &highest){
if(n>highest)highest=n;
   if(n==1)return 0;
   else if(n%2==0)return 1+conjecture(n/2,highest);
   else if(n%2==1)return 1+conjecture(n*3+1,highest);
}

int main(){
   long arr[]={9,19, 837,799 ,75,128,138,247, 942,488,749,153,153};
   long highest;
   int n = sizeof(arr)/sizeof(int);
   for(int i=0;i<n;i++){
       highest=-1;
       cout<<"n = "<<arr[i]<<" it took "<<conjecture(arr[i],highest)<<" steps\n";
       cout<<"Highest Number reached : "<<highest<<"\n\n";
   }

return 0;
}

//sample output

C:\Users\ IshuManish\Documents conjecture.exe -9 it took 19 steps ighest Number reached52 - 19 it took 20 steps ighest Number reached88 -837 it took 41 steps ighest Number reached 2512 - 799 it took 72 steps ighest Number reached 12148 -75 it took 14 steps ighest Number reached 340 - 128 it took 7 steps ighest Number reached 128 - 138 it took 15 steps ighest Number reached 208 - 247 it took 47 steps ighest Number reached 1672 - 942 it took 129 steps ighest Number reached 9232 -488 it took 22 steps ighest Number reached 488 -749 it took 46 steps ighest Number reached 2248 - 153 it took 36 steps ighest Number reached 520 -153 it took 36 steps ighest Number reached 520 rocess exited after 0.0646 seconds with return value 0 ress any key to continue - . -