UVA 100: The 3n + 1 problem

Problem hints: part-1:

Consider the following algorithm to generate a sequence of numbers. Start with an
integer n.If n is even, divide by 2. If n is odd, multiply by 3 and add 1. Repeat this process with the new value of n, terminating when n= 1. For example, the 

following sequence of numbers will be generated for n= 22:

22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

Explain:

a sequence of number: 

              Number and Number Sequence Meanings - 1111, 1212, 333, 666,1234 etc

Start with an integer n: 

              Let consider n is an integer number such as 1,2,3..etc

n is even, divide by 2: 

              if n is a even number such as 2,4,6,8...etc do n = n/2

n is odd, multiply by 3 and add 1:

              if n is a odd number such as 1,3,5...etc do n= 3*n+1

the new value of n:

              repeat for every new value of n such as if n = 4, then n = 4/2 = 2,

again for 2, n = 2/2 = 1 this way

terminating when n= 1:

              while n = 1, this loop will break

Conversion to code:

#include<stdio.h>

int main(){

int n = 20

printf("22 ");

while(n != 1) {
  if(n % 2 == 0) {
   n = n / 2;
  } else {
   n = n * 3 + 1;
  }

printf("%d ",n);
 }

}

Code result:

22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

Problem hints: part-2:

It is conjectured (but not yet proven) that this algorithm will terminate at n= 1 for

every integer n. Still, the conjecture holds for all integers up to at least 1,000,000.

For an input n, the cycle-length of n is the number of numbers generated up to and

including the 1. In the example above, the cycle length of 22 is 16. Given any two

numbers i and j, you are to determine the maximum cycle length over all numbers

between i and j, including both endpoints.

the cycle-length of n including the 1:
the cycle-length is a length which is counted by counting the number of times n is changed in the while loop including the n and upto where n =1

Conversion to code:

#include<stdio.h>

int cycle(int m) {
 int c = 1;
 while(m != 1) {
  c++;
  if(m % 2 == 0) {
   m = m / 2;
  } else {
   m = m * 3 + 1;
  }
 }
 return c;
}

Here if m = 22 then the cycle will be 16

Given any two

numbers i and j, you are to determine the maximum cycle length over all numbers

between i and j, including both endpoints.



giving any two number such as i=1 and j=10 determine maximum cycle length for i and j

such as 

for i = 1 length =1

for i = 2 length =2

for i = 3 length =8

for i = 4 length =3

for i = 5 length =6

for i = 6 length =9

for i = 7 length =17

for i = 8 length =4

for i = 9 length =20 ------max

for i = 10 length =7

so for i = 1 to 10 the max cycle length is 20

Full program:

#include<stdio.h>

int cycle(int m) {
 int c = 1;
 while(m != 1) {
  c++;
  if(m % 2 == 0) {
   m = m / 2;
  } else {
   m = m * 3 + 1;
  }
 }
 return c;
}

int main() {

 int a, b, c, abefore, bbefore, max;

 while(scanf("%d %d", &a, &b) == 2) {
  max = 0;
  abefore = a;
  bbefore = b;
  if(a > b) {
   c = a;
   a = b;
   b = c;
  }
  for(int i = a; i <= b; i++) {
   int t = cycle(i);
   if(max <= t) {
    max = t;
   }
  }
  printf("%d %d %d\n", abefore, bbefore, max);

 }
 return 0;
}