uva online judge 3n+1 problem solution python | uva 100

3n+1 problem (uva 100) is basically an even odd problem which can be stated as (from onlinejudge)

Consider the following algorithm:

           1. input n 

           2. print n 

           3. if n = 1 then STOP 

           4. if n is odd then n ←3n + 1 

           5. else n ←n/2 

           6. GOTO 2 

Given the input 22, the following sequence of numbers will be printed
           22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

It is conjectured that the algorithm above will terminate (when a 1 is printed) for any integral input value. Despite the simplicity of the algorithm, it is unknown whether this conjecture is true. It has been verified, however, for all integers n such that 0 < n < 1, 000, 000 (and, in fact, for many more numbers than this.)

        Given an input n, it is possible to determine the number of numbers printed before and including the 1 is printed. For a given n this is called the cycle-length of n. In the example above, the cycle length of 22 is 16.

        For any two numbers i and j you are to determine the maximum cycle length over all numbers between and including both i and j.

Sample Input
1 10
100 200
201 210
900 1000

Sample Output
1 10 20
100 200 125
201 210 89
900 1000 174

Explanation

It is very straight forward problem, for given input range i and j, we have to calculate maximum cycle length of numbers between i and j range. For every number n, calculate its odd even cycle length as, if n is odd, n -> 3*n + 1 else if n is even n -> n/2. Print the maximum cycle length among all numbers between i and j.

Example, for input 3 5 (i.e. 3 to 5)
for 3, cycle is 3, 10, 5, 16, 8, 4, 2, 1 (length = 8)
for 4, cycle is 4, 2, 1 (length = 3)
for 5, cycle is 5, 16, 8, 4, 2, 1 (length = 5)
Since, maximum length is 8, thus output will be 8.

Code:

def Cycle(i, j):
    max_length = 0
    for n in range(i, j+1):
        cycle = []
        while(True):
            cycle.append(n)
            if(n==1):
                break
            if(n%2==0):
                n = n//2
            else:
                n = (3*n)+1
        if(max_length < len(cycle)):
            max_length = len(cycle)
         
    return max_length

Z = input().split(" ")
i = int(Z[0])
j = int(Z[1])

cycle_length = Cycle(i, j)
print(cycle_length)

Here, input().split() method splits the inputs (by default blank space as identifier to separate inputs). Once i and j obtained it was passed to function Cycle().

In function Cycle(), max_length variable is used for storing maximum length, empty list 'cycle' is used to temporarily store obtained cycle.

In while loop if n==1, stop the itteration and check if obtained cycle length > max_length, if yes then update max_length = length of cycle. Finally return max_length.

Related keywords: 3n+1 problem,programming problem,3n+1,3n + 1 problem,uva 3n+1 problem,the 3n + 1 problem,solve 3n+1 problem,the 3n + 1 problem uva,100 - the 3n + 1 problem,3n+1 problem solution,100 problem uva,uva 100 - the 3n + 1 problem,100 - the 3n + 1 problem uva,3n+1 problem source code. 
#cybosocks-uva #3n+1 #uva-100-the-3n+1