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 twonumbers i and j, you are to determine the maximum cycle length over all numbersbetween 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; }